题目描述
字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列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的一个子序列。对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。
输入输出格式
输入格式：第1行为第1个字符序列，都是大写字母组成，以”.”结束。长度小于5000。
第2行为第2个字符序列，都是大写字母组成，以”.”结束，长度小于5000。
输出格式：第1行输出上述两个最长公共子序列的长度。
第2行输出所有可能出现的最长公共子序列个数，答案可能很大，只要将答案对100,000,000求余即可。
输入输出样例
输入样例#1： 复制
ABCBDAB. BACBBD.
输出样例#1： 复制
4 7
第一问就是一个普通的n^2的lcs 的dp
f[i][j]={max(f[i][j-1],f[i-1][j]) or f[i-1][j-1]+1(a[i]=b[j])}
第二问竟然用到了容斥定理：
我么你的f设的是第一个串的前i个第二个串的前j个的总方案书，这里就有了二位前缀和的意思，看代码比较容易理解：
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <iostream> 5 #define getmax(a,b) (((a)>(b))?(a):(b)) 6 using namespace std; 7 const int maxn=5005,mo=100000000; 8 int n,m,f[2][maxn],g[2][maxn]; 9 char a[maxn],b[maxn]; 10 int main() 11 { 12 scanf("%s%s",a+1,b+1); 13 a[0]=b[0]='#'; 14 n=strlen(a)-2,m=strlen(b)-2; 15 int cur=0; 16 for(int i=0;i<=m;i++) g[cur][i]=1; 17 18 for(int i=1;i<=n;i++) 19 { 20 cur^=1;g[cur][0]=1; 21 for(int j=1;j<=m;j++) 22 { 23 g[cur][j]=0; 24 f[cur][j]=getmax(f[1-cur][j],f[cur][j-1]); 25 26 if(a[i]==b[j]) 27 { int cnt=0; 28 f[cur][j]=getmax(f[cur][j],f[1-cur][j-1]+1); 29 g[cur][j]=g[1-cur][j-1]; 30 if(f[cur][j]==f[cur][j-1]) g[cur][j]+=g[cur][j-1],cnt++; 31 if(f[cur][j]==f[1-cur][j]) g[cur][j]+=g[1-cur][j],cnt++; 32 33 } 34 else 35 { int cnt=0; 36 if(f[cur][j]==f[1-cur][j]) g[cur][j]+=g[1-cur][j],cnt++; 37 if(f[cur][j]==f[cur][j-1]) g[cur][j]+=g[cur][j-1],cnt++; 38 if(cnt>1)if(f[1-cur][j-1]==f[cur][j]) g[cur][j]-=g[1-cur][j-1]; 39 } 40 g[cur][j]=(g[cur][j]+mo)%mo; 41 } 42 } 43 44 printf("%d\n%d\n",f[cur][m],g[cur][m]); 45 }