首页 > 代码库 > HDU 1503 Advanced Fruits(LCS变形且输出解)
HDU 1503 Advanced Fruits(LCS变形且输出解)
HDU 1503 Advanced Fruits(LCS变形且输出解)
http://acm.hdu.edu.cn/showproblem.php?pid=1503
题意:
给你两个字符串s1和s2, 要你输出它们的并串s. 其中s1是s的一个子序列且s2也是s的一个子序列且s是所有符合前面要求的最短字符串.
分析:
令dp[i][j]==x表示s1串的前i个字符和s2串的前j个字符组成的串的LCS长度为x.
我们先求出LCS的dp数组值. 然后按照POJ2250:
http://blog.csdn.net/u013480600/article/details/40743953
类似的DFS过程即可输出s串.
大体的思想是:
假设dfs(i,j)表示要输出i个字符(从0计数)和j个字符的串的并.
如果i==0或j==0, 那么直接输出剩余的另一个串并return即可.
否者(下面3个过程保证i>0且j>0):
如果s[i-1]==s[j-1], 那么先dfs(i-1,j-1),再输出一次s1[i-1](第一个串的第i个字符)即可.
如果s[i-1]!=s[j-1]时:
如果dp[i-1][j]>dp[i][j-1], dfs(i-1,j), 再输出s1[i-1]即可.
如果dp[i-1][j]<=dp[i][j-1], dfs(i,j-1), 再输出s2[j-1]即可.
(仔细体会上述过程)
AC代码:
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=100+5; int n,m; int dp[maxn][maxn]; char s1[maxn],s2[maxn]; void dfs(int i,int j) { if(i+j==0) return; else if(i==0)//s1串已经输出完毕 { for(int k=0;k<j;k++) printf("%c",s2[k]); return ; } else if(j==0)//s2串已经输出完毕 { for(int k=0;k<i;k++) printf("%c",s1[k]); return ; } //下面的递归保证i>0且j>0. if(s1[i-1]==s2[j-1]) dfs(i-1,j-1), printf("%c",s1[i-1]); else if(dp[i-1][j]>dp[i][j-1]) dfs(i-1,j),printf("%c",s1[i-1]); else dfs(i,j-1),printf("%c",s2[j-1]); } int main() { while(scanf("%s%s",s1,s2)==2) { //初始化 n=strlen(s1); m=strlen(s2); memset(dp,0,sizeof(dp)); //递推 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } //dfs+输出 dfs(n,m); printf("\n"); } return 0; }
HDU 1503 Advanced Fruits(LCS变形且输出解)