2775 -- 【HAOI2010】最長(zhǎng)公共子序列

Description

字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個(gè)字符（可能一個(gè)也不去掉）后所形成的字符序列。令給定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一個(gè)嚴(yán)格遞增下標(biāo)序列<i0，i1，…，ik-1>，使得對(duì)所有的j=0，1，…，k-1，有xij = yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個(gè)子序列。
　　對(duì)給定的兩個(gè)字符序列，求出他們最長(zhǎng)的公共子序列長(zhǎng)度，以及最長(zhǎng)公共子序列個(gè)數(shù)。

Input

第1行為第1個(gè)字符序列，都是大寫字母組成，以”.”結(jié)束。長(zhǎng)度小于5000。
　　第2行為第2個(gè)字符序列，都是大寫字母組成，以”.”結(jié)束，長(zhǎng)度小于5000。

Output

第1行輸出上述兩個(gè)最長(zhǎng)公共子序列的長(zhǎng)度。
　　第2行輸出所有可能出現(xiàn)的最長(zhǎng)公共子序列個(gè)數(shù)，答案可能很大，只要將答案對(duì)100,000,000求余即可。

Sample Input

ABCBDAB. BACBBD.

Sample Output

4 7

Hint

說明：若答對(duì)第1問，則得到總分的40%，若答對(duì)第2問，則得到總分的60%，若兩問都對(duì)則得到100%分?jǐn)?shù)。

Source

xinyue 寫不動(dòng)題解了，滾一下數(shù)組節(jié)省空間 code： 1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 using namespace std; 5 int g[5005][5005],f[5005][5005]; 6 int main() { 7 string A,B; 8 cin>>A>>B; 9 A=' '+A,B=' '+B; 10 int lena=A.size()-2; 11 int lenb=B.size()-2;int now=0; 12 // for(int i=1; i<=lena; i++)g[i][0]=1; 13 for(int i=0; i<=lenb; i++)g[0][i]=1; 14 for(int i=1; i<=lena; i++) { 15 now^=1;g[now][0]=1; 16 for(int j=1; j<=lenb; j++) { 17 g[now][j]=0; 18 f[now][j]=max(f[now^1][j],max(f[now][j-1],(f[now^1][j-1]+1)*(A[i]==B[j]?1:0))); 19 if(f[now][j]==f[now^1][j])g[now][j]+=g[now^1][j]; 20 if(f[now][j]==f[now][j-1])g[now][j]+=g[now][j-1]; 21 if(f[now][j]==f[now^1][j-1]+1&&A[i]==B[j])g[now][j]+=g[now^1][j-1]; 22 if(f[now][j]==f[now^1][j-1]&&A[i]!=B[j])g[now][j]-=g[now^1][j-1]; 23 g[now][j]%=100000000; 24 } 25 } 26 cout<<f[now][lenb]<<"\n"<<g[now][lenb]; 27 return 0; 28 }

over

轉(zhuǎn)載于:https://www.cnblogs.com/saionjisekai/p/9885766.html

總結(jié)

以上是生活随笔為你收集整理的10.31T4 HAOI2010最长公共子序列 计数+容斥原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。