pku + 1458 求最大公共子序列

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     char s1[501];
 9     char s2[501];
10     while ( scanf ( "%s",s1 ) != EOF ){
11     scanf ( "%s",s2 );
12     int s3[500][500];
13     int l1,l2;
14     l1 = strlen( s1 );
15     l2 = strlen( s2 );
16     for ( int i = 0; i != l1+1++i )
17         for ( int j = 0; j != l2 + 1++j  )
18             s3[i][j] = 0;
19     int max1 = 0;
20     for ( int i = 0; i != l1; ++i )
21         for ( int j = 0; j != l2; ++j )
22         {
23             if ( s1[i] == s2[j] )
24             {
25                 s3[i+1][j+1= s3[i][j] + 1;
26                 if ( s3[i+1][j+1> max1 )
27                     max1 = s3[i+1][j+1];
28             }
29             else 
30                 s3[i+1][j+1= max (s3[i+1][j], s3[i][j+1]);
31         }
32     printf ( "%d\n",max1 );
33     }
34     return 0;
35 }
36 

这题其实不难,思想很简单,就是记录下前一个字母的最长子序列!
哈哈~~虽然参考书后还是相比较久,但总算会了!

posted on 2010-04-04 14:44 haozi 阅读(195) 评论(0)  编辑 收藏 引用 所属分类: 动态规划


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜