题目：最长公共子序列
思路：
第一问就是最长公共子序列的朴素算法。
令f[i][j]表示a串匹配到了i，b串匹配到了j的最长公共子序列。
f[i][j]= f[i-1][j-1]+1 (a[i]=b[j])
f[i][j]= max(f[i-1][j]，f[i][j-1])
第二问，令g[i][j]表示a串匹配到了i，b串匹配到了j，最长公共子序列为f[i][j]的方案数。
滚动数组优化成g[2][j]。
令x=i%2，y=(i-1)%2。
if (a[i]==b[j]) {if (f[x][j]==f[y][j]) g[x][j]=(g[x][j]+g[y][j])%md;if (f[x][j]==f[x][j-1]) g[x][j]=(g[x][j]+g[x][j-1])%md;
} else {if (f[x][j]==f[y][j-1]) g[x][j]=(g[x][j]-g[y][j-1])%md;if (f[x][j]==f[y][j]) g[x][j]=(g[x][j]+g[y][j])%md;if (f[x][j]==f[x][j-1]) g[x][j]=(g[x][j]+g[x][j-1])%md;
}代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 5000
#define md 100000000int n,m;
char a[maxn+5]= {0},b[maxn+5]= {0};
int f[3][maxn+5]= {0},g[3][maxn+5]= {0};void readin() {for(int i=1;; i++) {bool flag=true;while(~scanf("%c",&a[i])) {if(a[i]=='.') {flag=false;break;}if(isalpha(a[i])) break;}if(!flag) {n=i;n--;break;}}for(int i=1;; i++) {bool flag=true;while(~scanf("%c",&b[i])) {if(b[i]=='.') {flag=false;break;}if(isalpha(b[i])) break;}if(!flag) {m=i;m--;break;}}for(int i=0;i<=m;i++) g[0][i]=1;g[1][0]=1;
}void dp() {for (int i=1; i<=n; i++) {int x=i%2;int y=(i-1)%2;for (int j=1; j<=m; j++) {if (a[i]==b[j]) {f[x][j]=f[y][j-1]+1;g[x][j]=g[y][j-1];if (f[x][j]==f[y][j]) g[x][j]=(g[x][j]+g[y][j])%md;if (f[x][j]==f[x][j-1]) g[x][j]=(g[x][j]+g[x][j-1])%md;} else {f[x][j]=max(f[x][j-1],f[y][j]);g[x][j]=0;if (f[x][j]==f[y][j-1]) g[x][j]=(g[x][j]-g[y][j-1])%md;if (f[x][j]==f[y][j]) g[x][j]=(g[x][j]+g[y][j])%md;if (f[x][j]==f[x][j-1]) g[x][j]=(g[x][j]+g[x][j-1])%md;}}}
}int main() {readin();dp();printf("%d\n%d\n",f[n%2][m],(g[n%2][m]%md+md)%md);return 0;
}