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