北航 1066 求最长公共子学列

 //===============================================================
 //此题是求最长公共子学列,但是和一般题不同的是,内存卡的很严,是80kb,所以,要考虑状态的压缩,
 //其实每次状态转移的时候都是用到了仅仅两个状态而已,故而用两个数组就可以保存所有有用的状态了
 //开始想了好多的办法,后来算了算,那些优化简直可笑,不压缩是不可能过的。
 //===============================================================
 1
#include <iostream>
 2#include <string>
 3#define MAXN 1005
 4using namespace std;
 5
 6int dp_1[MAXN];
 7int dp_2[MAXN];
 8string s_1;
 9string s_2;
10int main()
11{
12    freopen("acm.acm","r",stdin);
13    int t;
14    int i;
15    int j;
16    cin>>t;
17    while(t --)
18    {
19        cin>>s_1;
20        cin>>s_2;
21        for(i = 0; i <= s_1.length(); ++ i)
22        {
23            dp_1[i] = 0;
24        }

25        for(j = 0;j <= s_2.length(); ++ j)
26        {
27            dp_2[j] = 0;
28        }

29        for(i = 0; i < s_1.length(); ++ i)
30        {
31            for(j = 0; j < s_2.length(); ++ j)
32            {
33                if(s_1[i] == s_2[j])
34                {
35                    dp_1[j+1= dp_2[j] + 1;
36                }

37                else
38                {
39                    if(dp_2[j+1> dp_1[j])
40                    {
41                        dp_1[j+1= dp_2[j+1];
42                    }

43                    else
44                    {
45                        dp_1[j+1= dp_1[j];
46                    }

47                }

48            }

49            for(j = 0; j <= s_2.length(); ++ j)
50            {
51                dp_2[j] = dp_1[j];
52            }

53        }

54        //cout<<dp_1[s_1.length()]<<endl;
55        cout<<dp_1[s_2.length()]<<endl;
56
57    }

58}

59
60
61
62

posted on 2010-06-13 19:27 成大才子 阅读(160) 评论(1)  编辑 收藏 引用 所属分类: ACM

评论

# re: 北航 1066 求最长公共子学列 2010-06-13 19:28 成大才子

很好的小题。  回复  更多评论   


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


<2010年6月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

公告

关于更多关于成大才子,请访问http://hi.baidu.com/成大才子

常用链接

留言簿(1)

随笔档案

文章分类

文章档案

链接

搜索

最新评论

阅读排行榜

评论排行榜