2423: [HAOI2010]最长公共子序列

题目大意：

都是中文自己看吧，题目链接

题解：
对于第一问，f[i][j]表示第一串到i第二串到j的最长公共子串，

f[i][j]=f[i-1][j-1](a[i]==b[j]),f[i][j]=max(f[i-1][j],f[i][j-1])(a[i]!=b[j])

对于第二问，g[i][j]表示第一串到i第二串到j的方案数，

第一种情况(a[i]==b[j])

如果f[i][j]==f[i][j-1] g[i][j]+=g[i][j-1],如果f[i][j]==f[i-1][j] g[i][j]+=g[i-1][j]

不会有重复的情况， f[i−1][j−1] 不可能去更新 f[i−1][j],f[i][j−1] ，所以新产生的路径一定与之前的没有交集。 

第二种情况（a[i]!=b[j])

如果f[i][j]==f[i][j-1] g[i][j]+=g[i][j-1],如果f[i][j]==f[i-1][j] g[i][j]+=g[i-1][j] 

最后还要减去 如果f[i][j]==f[i-1][j-1] g[i][j]-=g[i-1][j-1]

为什么，想想就懂了吧。。。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define mod 100000000
const int N=5110;
char s1[N],s2[N];
int n,m;
int f[2][N],g[2][N];
int main()
{
scanf("%s%s",s1+1,s2+1);
n=strlen(s1+1);m=strlen(s2+1);n--;m--;
for(int i=0;i<=m;i++) g[0][i]=1;
g[1][0]=1;int mar=0;
//printf("%d %d\n",n,m);
for(int i=1;i<=n;i++)
{
mar^=1;
for(int j=1;j<=m;j++)
{
if(s1[i]==s2[j])
{
f[mar][j]=f[mar^1][j-1]+1;
g[mar][j]=g[mar^1][j-1];
g[mar][j]+=(f[mar][j]==f[mar][j-1])*g[mar][j-1];
g[mar][j]+=(f[mar][j]==f[mar^1][j])*g[mar^1][j];
}
else
{
f[mar][j]=max(f[mar^1][j],f[mar][j-1]);
g[mar][j]=(f[mar][j]==f[mar^1][j])*g[mar^1][j];
g[mar][j]+=(f[mar][j]==f[mar][j-1])*g[mar][j-1];
g[mar][j]-=(f[mar^1][j-1]==f[mar][j])*g[mar^1][j-1];
}
g[mar][j]%=mod;
}
}
g[mar][m]+=mod;g[mar][m]%=mod;
printf("%d\n%d",f[mar][m],g[mar][m]);
}