bon

C++博客 :: 首頁(yè) :: 聯(lián)系 :: 聚合

:: 管理

46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

常用鏈接

留言簿(2)

我參與的團(tuán)隊(duì)

隨筆分類(lèi)

隨筆檔案

搜索

閱讀排行榜

評(píng)論排行榜

最長(zhǎng)公共子序列（pku 1936）

這一篇講我對(duì)最長(zhǎng)公共子序列（LCS）的理解，之前只是強(qiáng)記了公式，現(xiàn)在有了較好的理解。

主要是要理解這個(gè)問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

設(shè)序列 $X=\{x_{1},\dots,x_{m}\}$ 和 $Y=\{y_{1},\dots,y_{n}\}$ 的LCS是 $Z=\{z_{1},\dots,z_{k}\}$ ，則

(1) 若 $x_{m}=y_{n}$ ，則 $z_{k}=x_{m}=y_{n}$ ，且 $Z_{k-1}$ 是 $X_{m-1}$ 與 $Y_{n-1}$ 的LCS；

(2) 若 $x_{m}\neq y_{n}$ ，且 $x_{m}\neq z_{k}$ ，則 $Z_{k}$ 是 $X_{m-1}$ 與 $Y_{n}$ 的LCS；

(3) 若 $x_{m}\neq y_{n}$ ，且 $y_{n}\neq z_{k}$ ，則 $Z_{k}$ 是 $X_{m}$ 與 $Y_{n-1}$ 的LCS 。

證明：(1) 若 $x_{m}\neq z_{k}$ ，說(shuō)明在 $Z=\{z_{1},\dots,z_{k}\}$ 的后面加上 $x_{m}=y_{n}$ ，可以得到一個(gè)長(zhǎng)為k+1的新序列： $Z_{k+1}=\{z_{1},\dots,z_{k},x_{m}\}$ ，這與 $Z_{k}$ 是 $X_{m}$ 與
                   $Y_{n}$ 的LCS矛盾。另外若 $Z_{k-1}$ 不是 $X_{m-1}$ 與 $Y_{n-1}$ 的LCS，那么我們只用 $X_{m-1}$ 與 $Y_{n-1}$ 就可以得到一個(gè)長(zhǎng)度至少為k的子序列，再這個(gè)子序列
                  后面再加上 $x_{m}=y_{n}$ ，就可以用 $X_{m}$ 與 $Y_{n}$ 構(gòu)造得到一個(gè)長(zhǎng)為k+1的子序列，這也產(chǎn)生了矛盾。

            (2) 若 $X_{m-1}$ 與 $Y_{n}$ 有比 $Z_{k}$ 更長(zhǎng)的LCS，則這個(gè)LCS同樣是 $X_{m}$ 與 $Y_{n}$ 的一個(gè)長(zhǎng)于k的LCS，矛盾。(3)的證明類(lèi)似。

思考：(2)中的結(jié)論" $Z_{k}$ 是 $X_{m-1}$ 與 $Y_{n}$ 的LCS "能否改成" $Z_{k}$ 是 $X_{m-2}$ 與 $Y_{n}$ 的LCS" 呢？因?yàn)?img src="http://www.forkosh.dreamhost.com/mathtex.cgi?x_{m-1}">可能是 $Z_{k}$ 最后一個(gè)元素，那么 $X_{m-2}$ 與 $Y_{n}$ 的LCS就不是
                   $Z_{k}$ 了，而是更小的一個(gè)序列。

                  其實(shí)(2)的條件暗示著 $z_{k}$ 可能就是 $y_{n}$ ，當(dāng)然也有可能不是，但是不管怎么樣， $Z_{k}$ 肯定是 $X_{m-1}$ 與 $Y_{n}$ 的LCS。

                  下面的圖說(shuō)明了這兩種情況：

由此我們可以得到如下的狀態(tài)轉(zhuǎn)移方程：

下面就是題目代碼啦，很簡(jiǎn)單，沒(méi)什么好說(shuō)的。

1 #include <iostream>
2
3 using namespace std;
4
5 char a[100001],b[100001];
6
7 void dp()
8 {
9     int n=strlen(a),m=strlen(b);
10     int i,j;
11     int d[2][100000];
12     int flag=1;
13     for(i=0;i<=n;i++) d[0][i]=0;
14     for(i=1;i<=m;i++){
15         for(j=0;j<=n;j++){
16             if(j==0) d[flag][j]=0;
17             else{
18                 if(b[i-1]==a[j-1]) d[flag][j]=d[1-flag][j-1]+1;
19                 else{
20                     d[flag][j]=(d[flag][j-1]>d[1-flag][j])?d[flag][j-1]:d[1-flag][j];
21                 }
22             }
23             //printf("%d ",d[flag][j]);
24         }
25         //printf("\n");
26         flag=1-flag;
27     }
28     //printf("%d\n",d[1-flag][n]);
29     if(d[1-flag][n]==n)    printf("Yes\n");
30     else printf("No\n");
31     return;
32 }
33
34 int main()
35 {
36     while(cin>>a>>b){
37         dp();
38     }
39     return 1;
40 }

posted on 2008-05-27 15:46 bon 閱讀(787) 評(píng)論(0) 編輯收藏引用

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



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

bon