2423: [HAOI2010]最长公共子序列
Time Limit: 10 SecDescription
字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列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.
BACBBD.
Sample Output
4
7
7
【题解】
参照一般的最长公共子序列的做法
if s1[i]==s2[j] then f[i][j]=f[i-1][j-1]+1
else f[i][j]=max(f[i][j-1],f[i-1][j])
然后我们用g[i][j]来表示方案数。
对于s1[i]==s2[i]
g[i][j]=g[i-1][j-1]+k1*g[i-1][j]+k2*g[i][j-1]
f[i][j]=f[i-1][j] then k1=1 else k1=0;
f[i][j]=f[i][j-1] then k2=1 else k2=0;
对于s1[i]!=s2[i]
g[i][j]=g[i-1][j-1]+k1*g[i-1][j]+k2*g[i][j-1]-k3*g[i-1][j-1]
f[i][j]=f[i-1][j] then k1=1 else k1=0;
f[i][j]=f[i][j-1] then k2=1 else k2=0;
f[i][j]=f[i-1][j-1] then k3=1 else k3=0;
然后上去发现MLE!!!
就开了开滚动数组TAT
然后写跪了QAQ
1 #include <stdio.h> 2 #include <string.h> 3 #include<iostream> 4 #define max(a,b) a>b?a:b 5 using namespace std; 6 const int MOD=100000000; 7 int f[2][5001],g[2][5001]; 8 char s1[5001],s2[5002]; 9 int len1,len2; 10 int main() { 11 scanf("%s%s",s1,s2); 12 len1=strlen(s1); 13 len2=strlen(s2); 14 for (int i=len1-1;i>=1;--i) s1[i]=s1[i-1]; 15 for (int i=len2-1;i>=1;--i) s2[i]=s2[i-1]; 16 len1--;len2--; 17 int pre=0,now=1; 18 for (int i=1;i<=len2;i++) 19 g[0][i]=1; 20 g[pre][0]=1; 21 for (int i=1;i<=len1;++i) { 22 for (int j=1;j<=len2;++j) f[now][j]=g[now][j]=0; 23 g[now][0]=1; 24 for (int j=1;j<=len2;++j) 25 if(s1[i]==s2[j]) { 26 f[now][j]=f[pre][j-1]+1; 27 g[now][j]=g[pre][j-1],g[now][j]%=MOD; 28 if (f[now][j]==f[pre][j]) g[now][j]+=g[pre][j],g[now][j]%=MOD; 29 if (f[now][j]==f[now][j-1]) g[now][j]+=g[now][j-1],g[now][j]%=MOD; 30 } 31 else { 32 f[now][j]=max(f[pre][j],f[now][j-1]); 33 if (f[now][j]==f[pre][j]) g[now][j]+=g[pre][j],g[now][j]%=MOD; 34 if (f[now][j]==f[now][j-1]) g[now][j]+=g[now][j-1],g[now][j]%=MOD; 35 if (f[now][j]==f[pre][j-1]) g[now][j]-=g[pre][j-1],g[now][j]=(g[now][j]+MOD)%MOD; 36 }//cout<<i<<" "<<j<<" "<<f[now][j]<<" "<<g[now][j]<<endl;} 37 int t=pre;pre=now;now=t; 38 } 39 printf("%d %d ",f[pre][len2],g[pre][len2]); 40 return 0; 41 }