【51nod】1006最长公共子序列Lcs

1006 最长公共子序列Lcs基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题 收藏 关注

第1行：字符串A
第2行：字符串B
(A,B的长度 <= 1000)

输出最长的子序列，如果有多个，随意输出1个。

abcicba
abdkscab

abca

动态规划问题

#include
#include
int dp[1010][1010];
int max(int a,int b,int c)
{
a=a>b?a:b;
return a>c?a:c;
}
int main()
{
char a[1010],b[1010],c[1010];int lena,lenb,j,k,i,u;
while(scanf("%s%s",a+1,b+1)!=EOF)
{
lena=strlen(a+1),lenb=strlen(b+1);
for(j=1;j<=lena;j++)
for(k=1;k<=lenb;k++)
dp[j][k]=max(dp[j-1][k-1]+(a[j]==b[k]?1:0),dp[j-1][k],dp[j][k-1]);
j--;k--;u=0;
while(dp[j][k]>0)
{
if(a[j]==b[k])
{
c[u++]=a[j];
if(dp[j][k]==1) break;
--j,--k;
}
else if(dp[j-1][k]==dp[j][k])
--j;
else
--k;
}
for(i=dp[lena][lenb]-1;i>=0;i--)
{
printf("%c",c[i]);
}printf("\n");
}

return 0;
}