P2516 [HAOI2010] 最长公共子序列
teafrogsf
2017-12-25 20:36:05
这是我们很久以前的训练题。
一开始我看到题目名字的时候，以为像某些命名为线段树/树状数组/单旋等某些省选题一样根本不是用这个东西写题，但看着看着就发现第一问**神TM就是裸LCS**······
f[i][j]定义是LCS，ans[i][j]指a前i字母b前j字母的方案数。
然后第二问主要取决于f[i-1][j-1],f[i][j-1],f[i=1][j=1]与f[i][j]的相等性。
当f[i][j]==f[i-1][j]/f[i][j-1]的时候，直接加上对应的ans就可以了；
当f[i][j]=f[i-1][j-1]+1的时候，ans也加；
当f[i][j]==f[i-1][j-1]时则要把对应的ans[i-1][j-1]的方案减去。
然后不要忘了取模、字符串长度要减1。
代码难度不大，重在脑补理解。
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#define f(i,a,b) for(register int i=a;i<=b;++i)
int f[2][5010],ans[2][5010],n,m;
const int mod=1e8;
char a[5010],b[5010];
int now=1,pre;
int main()
{
// freopen("lcs.in","r",stdin);
// freopen("lcs.out","w",stdout);
scanf("%s%s",a+1,b+1);
n=strlen(a+1)-1,m=strlen(b+1)-1;
ans[1][0]=1;f(i,0,m)ans[0][i]=1;
f(i,1,n)
{
f(j,1,m)
{
f[now][j]=std::max(f[pre][j],f[now][j-1]);
ans[now][j]=0;
if(a[i]==b[j])
{
f[now][j]=std::max(f[now][j],f[pre][j-1]+1);
if(f[now][j]==f[pre][j-1]+1)ans[now][j]+=ans[pre][j-1];
}
if(f[pre][j]==f[now][j])ans[now][j]+=ans[pre][j];
if(f[now][j-1]==f[now][j])ans[now][j]+=ans[now][j-1];
if(f[pre][j-1]==f[now][j])ans[now][j]-=ans[pre][j-1];
ans[now][j]%=mod;
}now=pre,pre^=1;
}
printf("%d\n%d\n",f[pre][m],(ans[pre][m]+mod)%mod);
}
```