NYOJ 36 最长公共子序列

http://acm.nyist.net/JudgeOnline/problem.php?pid=36

今天突然想到那天文哥给我看的最长公共子序列的问题....然后自己找了这道题来看看..
那天文哥叫我看的时候, 自己就这么一下扫过去. 没什么概念.

今天自己从头按照它的分析方法来分析了下.

f[i][j] 表示 s1 的 i 个字符和 s2 的 j 个字符内最长的公共子序列

if(s1[i] == s2[j]) f[i][j] = f[i-1][j-1] + 1;

else f[i][j] = max(f[i-1][j], f[i][j-1]);

当不相同的时候，则考虑在 s1 的 i 个字符和 s2 的 j 个字符内最长的公共子序列.

可用 s1 的 i -1 个字符和 s2 的 j 个字符内最长的公共子序列长度和 s1 的 i 个字符和 s2 的 j -1 个字符内最长的公共子序列长度的最大值.

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define maxn 1001
 4 char s1[maxn], s2[maxn];
 5 int ans[maxn][maxn];
 6 int max(int a, int b)
 7 {
 8     return a > b ? a : b;
 9 }
10 int main()
11 {
12     int i, j, t, len1, len2, mark;
13     scanf("%d",&t);
14     while(t--)
15     {
16         scanf("%s%s",s1,s2);
17         len1 = strlen(s1);
18         len2 = strlen(s2);
19         for(i = 0; i <= len1; i++)
20         for(j = 0; j <= len2; j++)
21         ans[i][j] = 0;
22         mark = 0;
23         for(i = 1; i <= len1; i++)
24         {
25             for(j = 1; j <= len2; j++)
26             {
27                 if(s1[i-1]==s2[j-1])
28                 {
29                     ans[i][j] = ans[i-1][j-1]+1;
30                 }
31                 else
32                    ans[i][j] = max(ans[i-1][j], ans[i][j-1]);
33                 if(mark < ans[i][j])  mark = ans[i][j];   
34             }
35         }
36         printf("%d\n",mark);
37     }
38     return 0;
39 }