题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2423
题目大意：求两个字符串的最长公共子序列长度和最长公共子序列个数。
这道题的话，对于神犇来说，肯定是一眼看出状态转移方程的。而我这个蒟蒻，看了几篇博客之后才看懂。。。
第一问模板lcs，大家肯定都会，就是设f[i][j]为A串跑到第i位，B串跑到第j为时的最长公共子序列长度，然后就有：
f[i][j]=f[i-1][j-1]+1 (a[i]==b[j])
=max(f[i-1][j],f[i][j-1]) (a[i]!=b[j]) （原谅我不会编辑公式）
我就解释一下第二问的方程。先设g[i][j]为A串跑到第i位，B串跑到第j为时的最长公共子序列个数，方程就是这样：
g[i][j]=g[i-1][j-1]
+g[i-1][j] (f[i][j]==f[i-1][j])
+g[i][j-1] (f[i][j]==f[i][j-1])
(a[i]==b[j])
=g[i-1][j] (f[i][j]==f[i-1][j])
+g[i][j-1] (f[i][j]==f[i][j-1])
-g[i-1][j-1] (f[i][j]==f[i-1][j-1])
(a[i]!=b[j])
这里当a[i]和b[j]相同时，g[i-1][j],g[i-1][j-1],g[i][j-1]这三个的最长公共子序列不会重复，因为这里的g[i-1][j-1]实际上还要在末尾添加上a[i]（或b[j]），因此这些lcs全都是以a[i],b[j]结尾的，而g[i-1][j]不包含以a[i]结尾的lcs，g[i][j-1]不包含以b[j]结尾的lcs，因此这三类lcs不会重复，可以直接相加。
当a[i]与b[j]不同时，最后当f[i][j]==f[i-1][j-1]时要减去g[i-1][j-1]就是因为这时g[i-1][j-1]被分别包含在g[i-1][j]和g[i][j-1]中，算了两次，要把重复的减掉。
于是就可以愉快地AC这道题了。
还有，一定要用滚动数组，不然爆！空！间！
丑代码：
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int mod=100000000; int f[2][5010],g[2][5010]; char a[5010],b[5010]; int main() { int i,j,n,m; 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++) for(j=1;j<=m;j++) if(a[i-1]==b[j-1]){ f[i&1][j]=f[i&1^1][j-1]+1; g[i&1][j]=(g[i&1^1][j-1]+(f[i&1^1][j]==f[i&1][j])*g[i&1^1][j]+(f[i&1][j-1]==f[i&1][j])*g[i&1][j-1])%mod; } else{ if(f[i&1^1][j]>f[i&1][j-1])f[i&1][j]=f[i&1^1][j];else f[i&1][j]=f[i&1][j-1]; g[i&1][j]=((f[i&1^1][j]==f[i&1][j])*g[i&1^1][j]+(f[i&1][j-1]==f[i&1][j])*g[i&1][j-1]-(f[i&1][j]==f[i&1^1][j-1])*g[i&1^1][j-1]+mod)%mod; } printf("%d %d",f[n&1][m],g[n&1][m]); }