| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
解题报告O(n^2)LCS+dfs
题目大意:
两个字符串,字典升序输出LCS的所有情况
思路:
对于两个固定的字符串来说,LCS的大小随当前处理的长度不下降增加
从状态转移方程可以看出,dp[i][j]不小于dp[i-1][j],dp[i][j-1]和dp[i-1][j-1],
因此我们可以根据这条单调性对已处理好的LCS进行操作,(显然,LCS是少不了的) O(mn)++;
Alice[i][j]/Bob[i][j] 记录两个字符串中26个英文字母对应长度中最后出现的位置
由上述可知,对于相同的字母,下标越靠后
再用dfs去枚举所有情况,最后排序输出(也可以一开始就按字典序去搜字母,省去排序的步骤)
(感觉除了LCS,并不算DP)~
简要实现:
LCS略
for(int i=1;i<=la;i++){
for(int j=1;j<=26;j++){
ail[i][j]=ail[i-1][j];
}
ail[i][a[i]-96]=i;
}
Bob同理
void dfs(int al,int bl,int l){//a中处理位置,b中处理位置,匹配长度
if(l==dp[la][lb]){
strcpy(ans[sum++],p);//匹配成功,记录结果
return ;
}
if(dp[al][bl]+l<dp[la][lb])return ;//不符合LCS
if(al<0||bl<0)return ;//边界
for(int i=1;i<=26;i++) {
if(ail[al][i]>0&&bob[bl][i]>0) //存在同一个公共字母
dfs(ail[al][i]-1,bob[bl][i]-1,l+1);//从公共字母的前一个继续搜索
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator