10.31T4 HAOI2010最長公共子序列計數+容斥原理

2775 -- 【HAOI2010】最長公共子序列

Description

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

Input

第1行為第1個字符序列，都是大寫字母組成，以”.”結束。長度小于5000。
　　第2行為第2個字符序列，都是大寫字母組成，以”.”結束，長度小于5000。

Output

第1行輸出上述兩個最長公共子序列的長度。
　　第2行輸出所有可能出現的最長公共子序列個數，答案可能很大，只要將答案對100,000,000求余即可。

Sample Input

ABCBDAB.

BACBBD.

Sample Output

Hint

說明：若答對第1問，則得到總分的40%，若答對第2問，則得到總分的60%，若兩問都對則得到100%分數。

Source

xinyue

寫不動題解了，滾一下數組節省空間

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

轉載于:https://www.cnblogs.com/saionjisekai/p/9885766.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/281758.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/281758.shtml
英文地址，請注明出處：http://en.pswp.cn/news/281758.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！