2697 - [HAOI2010]最长公共子序列
字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列x=“x0，x1，…，xn-1”， 序列Y=“y0，y1，…，yk-1是X的子序列，存在X的一个严格递增下标序 列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k- 1，有xij="yj。 例如，x=“ABCBDAB”，Y=“BCDB”是X的一个子序列。
对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。</i0，i1，…，ik-1>，使得对所有的j=0，1，…，k->
</p>
Input
第1行为第1个字符序列，都是大写字母组成，以”.”结束。长度小于5000。
第2行为第2个字符序列，都是大写字母组成，以”.”结束，长度小于5000。
Output
第1行输出上述两个最长公共子序列的长度。
第2行输出所有可能出现的最长公共子序列个数，答案可能很大，只要将答案对100，000，000求余即可。
Examples
Input
ABCBDAB. BACBBD.
Output
4 7
Solution C
#include "stdio.h" #include "string.h" #define N 5005 #define M 100000000 int n,m; char a[N],b[N]; int f[2][N],g[2][N]; int max(int a,int b){if(a>b)return a;return b;} int main() { int i,j,k; scanf("%s%s",a,b); n=strlen(a)-1; m=strlen(b)-1; for(i=0;i<=m;i++)g[0][i]=1;g[1][0]=1; for(i=1;i<=n;i++) { k=i&1; for(j=1;j<=m;j++) { if(a[i-1]==b[j-1])f[k][j]=f[!k][j-1]+1,g[k][j]=g[!k][j-1]; else f[k][j]=max(f[!k][j],f[k][j-1]),g[k][j]=0; if(f[k][j]==f[!k][j])g[k][j]+=g[!k][j]; if(f[k][j]==f[k][j-1])g[k][j]+=g[k][j-1]; if(f[k][j]==f[!k][j-1])g[k][j]-=g[!k][j-1]; g[k][j]=(g[k][j]+M)%M; } } printf("%d\n%d\n",f[k][m],g[k][m]); return 0; }
Solution C++
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int m=(int)1E8; string s1,s2; int f[2][5001]={0},g[2][5001]={0}; void init(); void work(); int my_max(int,int); int main() { //freopen("lcs5.in","r",stdin); //freopen("a.txt","w",stdout); init(); work(); return 0; } void init() { cin>>s1; cin>>s2; } void work() { int len1=s1.size()-1,len2=s2.size()-1; //cout<<len1<<' '<<len2<<endl; for(int i=0;i<=len2;i++)g[0][i]=1; //f[0][0]=1; int k; for(int i=1;i<=len1;i++) { k=i & 1; memset(g[k],0,sizeof(g[k])); memset(f[k],0,sizeof(f[k])); g[k][0]=1; g[!k][0]=1; for(int j=1;j<=len2;j++) { if(s1[i-1]==s2[j-1]) { f[k][j]=f[!k][j-1]+1; g[k][j]=g[!k][j-1]; g[k][j]%=m; if(f[k][j]==f[!k][j]) { g[k][j]+=g[!k][j]; g[k][j]%=m; } if(f[k][j-1]==f[k][j]) { g[k][j]+=g[k][j-1]; g[k][j]%=m; } } else { if(f[!k][j]>f[k][j-1]) { f[k][j]=f[!k][j]; g[k][j]+=g[!k][j]; g[k][j]%=m; } if(f[!k][j]<f[k][j-1]) { f[k][j]=f[k][j-1]; g[k][j]+=g[k][j-1]; g[k][j]%=m; } if(f[!k][j]==f[k][j-1]) { f[k][j]=f[!k][j]; g[k][j]+=g[!k][j]+g[k][j-1]; if(f[!k][j-1]==f[k][j])g[k][j]-=g[!k][j-1]; g[k][j]=(g[k][j]+3*m)%m; } } //cout<<j<<' '<<g[k][j]<<endl; } } cout<<f[k][len2]<<endl; cout<<g[k][len2]<<endl; } int my_max(int x,int y) { if(x>y)return x; else return y; }