HDU 1503 最长公共子序列问题---加强版（路径打印）dp

﹏ヽ暗。殇╰゛Y 2024-02-17 19:25 8阅读 0赞

题意：给两个字符串，要找出满足条件的最短串，条件是最长公共子序列只能出现一次。

思路：先找出最长公共子序列，用数组dp\[i\]\[j\]记录一个字符串长度为i,第二个长度为j此状态下最长公共子序列个数，用pre\[\]\[\]保存dp\[\]\[\]通过哪一个子问题求得，以决定搜索方向

:具体三种状态请参考（http://blog.csdn.net/yysdsyl/article/details/4226630）。输出时要注意最长公共子序列的各元素保持原来字符串里的相对位置（即前面的还是前面，后面的

还是后面，中间的还是中间）其他字符顺序不要求。如pear peach 可以输出pearch或peachr。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=100+10;
    int dp[maxn][maxn];
    int pre[maxn][maxn];
    char s1[maxn],s2[maxn];
    
    void print(int i,int j){
    	if(i==0 && j==0)return ;
    	if(pre[i][j]==0){
    		print(i-1,j-1);
    		printf("%c",s1[i-1]);   //s2[j-1]也可 
    	}
    	else if(pre[i][j]==1){
    		print(i-1,j);
    		printf("%c",s1[i-1]);
    	}
    	else {
    		print(i,j-1);
    		printf("%c",s2[j-1]);
    	}
    }
    int main(){
    	while(scanf("%s%s",s1,s2)==2){
    		int len1=strlen(s1);
    		int len2=strlen(s2);
    		memset(dp,0,sizeof(dp));
    		
    		for(int i=1;i<=len1;i++)pre[i][0]=1;
    		for(int j=1;j<=len2;j++)pre[0][j]=-1;
    		
    		for(int i=1;i<=len1;i++)
    			for(int j=1;j<=len2;j++)
    			   if(s1[i-1]==s2[j-1]){
    			   	dp[i][j]=dp[i-1][j-1]+1;     //dp[i][j]表示第一个字符串长度为i,第二个长度为j此状态下最长公共子序列个数 
    			   	pre[i][j]=0;
    			   }
    			   else if(dp[i-1][j]>=dp[i][j-1]){
    			   	dp[i][j]=dp[i-1][j];
    			   	pre[i][j]=1;
    			   }
    			   else {
    			   	dp[i][j]=dp[i][j-1];
    			   	pre[i][j]=-1;
    			   }
    			   
    			   print(len1,len2);
    			   printf("\n");
    	}
    	return 0;
    }