第一问直接dp求
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]来表示方案数。
对于A[i]==B[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;
对于A[i]!=B[i]
g[i][j]=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;
注意 ：
1. 要用滚动数组否则MLE！！
2. 别忘记初始化g数组（否则，呵呵…..就因为这个问题调了好长时间……）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#define M 100000000
#define T 5555
using namespace std;
char A[T],B[T];
int g[2][T],f[2][T];
int n,m;
int main()
{
scanf("%s%s",A+1,B+1);
n=strlen(A+1)-1;
m=strlen(B+1)-1;
for(int i=0; i<=m; i++) g[0][i]=1;
g[1][0]=1;
for(int i=1; i<=n; i++)
{
int nw=i&1,l=nw^1;
for(int j=1; j<=m; j++)
{
if(A[i]==B[j])
{
f[nw][j]=f[l][j-1]+1;
g[nw][j]=g[l][j-1];
if(f[nw][j]==f[l][j]) g[nw][j]=(g[nw][j]+g[l][j])%M;
if(f[nw][j]==f[nw][j-1]) g[nw][j]=(g[nw][j]+g[nw][j-1])%M;
}
else
{
f[nw][j]=max(f[l][j],f[nw][j-1]);
g[nw][j]=0;
if(f[nw][j]==f[l][j]) g[nw][j]=(g[nw][j]+g[l][j])%M;
if(f[nw][j]==f[nw][j-1]) g[nw][j]=(g[nw][j]+g[nw][j-1])%M;
if(f[nw][j]==f[l][j-1]) g[nw][j]=(g[nw][j]-g[l][j-1])%M;
}
//cout << i << " " << j <<": " << f[nw][j] <<" "<< g[nw][j] << endl;
}
}
int l=n&1;
g[l][m]=(g[l][m]+M)%M;
cout <<f[l][m] << endl << g[l][m];
return 0;
}