hdu 1159 Common Subsequence

http://acm.hdu.edu.cn/showproblem.php?pid=1159

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 1000
 5 using namespace std;
 6 
 7 int dp[maxn][maxn];
 8 char str1[maxn];
 9 char str2[maxn];
10 
11 int main()
12 {
13     while(scanf("%s %s",str1,str2)!=EOF)
14     {
15         int k1=strlen(str1);
16         int k2=strlen(str2);
17         memset(dp,0,sizeof(dp));
18         for(int i=1; i<=k1; i++)
19         {
20             for(int j=1; j<=k2; j++)
21             {
22                 if(str1[i-1]==str2[j-1])
23                     dp[i][j]=dp[i-1][j-1]+1;
24                 else
25                     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
26             }
27         }
28         printf("%d
",dp[k1][k2]);
29     }
30     return 0;
31 }

View Code