久久精品国产免费,国产主播一区二区三区,久久美女性网

Microsoft.Cpp.Chengdacaizi

天行健，君子以自強(qiáng)不息地勢(shì)坤，君子以厚德載物

北航 1066 求最長公共子學(xué)列

 //===============================================================
 //此題是求最長公共子學(xué)列，但是和一般題不同的是，內(nèi)存卡的很嚴(yán)，是80kb,所以，要考慮狀態(tài)的壓縮，
 //其實(shí)每次狀態(tài)轉(zhuǎn)移的時(shí)候都是用到了僅僅兩個(gè)狀態(tài)而已，故而用兩個(gè)數(shù)組就可以保存所有有用的狀態(tài)了
 //開始想了好多的辦法，后來算了算，那些優(yōu)化簡(jiǎn)直可笑，不壓縮是不可能過的。
 //===============================================================
 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 成大才子閱讀(197) 評(píng)論(1) 編輯收藏引用所屬分類: ACM

評(píng)論

# re: 北航 1066 求最長公共子學(xué)列 2010-06-13 19:28 成大才子

很好的小題。回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

<

2011年1月

>

日

一

二

三

四

五

六

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

導(dǎo)航

統(tǒng)計(jì)

隨筆 - 16
文章 - 1
評(píng)論 - 4
引用 - 0

公告

關(guān)于更多關(guān)于成大才子，請(qǐng)?jiān)L問http://hi.baidu.com/成大才子

# re: 北航 1066 求最長公共子學(xué)列 2010-06-13 19:28 成大才子

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

北航 1066 求最長公共子學(xué)列

評(píng)論

導(dǎo)航

統(tǒng)計(jì)

公告

常用鏈接

留言簿(1)

隨筆檔案

文章分類

文章檔案

鏈接

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜