bzoj 2423 [HAOI2010]最长公共子序列动态规划

本文主要是介绍bzoj 2423 [HAOI2010]最长公共子序列动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列 < i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij = yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。
Input

第1行为第1个字符序列，都是大写字母组成，以”.”结束。长度小于5000。
第2行为第2个字符序列，都是大写字母组成，以”.”结束，长度小于5000。
Output

第1行输出上述两个最长公共子序列的长度。
第2行输出所有可能出现的最长公共子序列个数，答案可能很大，只要将答案对100,000,000求余即可。
Sample Input

ABCBDAB.

BACBBD.
Sample Output

7
HINT

传送门
……不咋会orz = =。。
设第一个字符串是A，第二个字符串是B，考虑一下dp：
f[i][j]表示A前i位，B前j位的最长公共子序列长度。
那么考虑当前位置匹不匹配，写出方程：

f [i] [j] = m a x (f [i - 1] [j], f [i] [j - 1]) 当 A i = B j ， f [i] [j] = m a x (f [i] [j], f [i - 1] [j - 1] + 1)

$f[i][j]=max(f[i-1][j],f[i][j-1])\\ 当Ai=Bj，f[i][j]=max(f[i][j],f[i-1][j-1]+1)$
那么第二问该咋办呢……
用g[i][j]表示A前i位，B前j位的最长公共子序列数目。
……g[i][j]如何转移呢。。想法比较明显，就是考虑从哪里转过来，
那么比如

f[i][j]=f[i−1][j] $f[i][j]=f[i-1][j]$ ，就可以认为从f[i-1][j]转移过来，
g[i][j]累计上g[i-1][j]；
那么根据这个思路，写出来就是下面酱紫的：

当 f [i] [j] = f [i - 1] [j] ， g [i] [j] + = g [i - 1] [j] 当 f [i] [j] = f [i] [j - 1] ， g [i] [j] + = g [i] [j - 1] 当 A i = B j 且 f [i] [j] = f [i - 1] [j - 1] + 1 ， g [i] [j] + = g [i - 1] [j - 1]

$当f[i][j]=f[i-1][j]，g[i][j]+=g[i-1][j]\\ 当f[i][j]=f[i][j-1]，g[i][j]+=g[i][j-1]\\ 当Ai=Bj且f[i][j]=f[i-1][j-1]+1，g[i][j]+=g[i-1][j-1]$
……看上去没问题啊喂，然而样例错掉了= =
初始化

g[i][0]=g[0][i]=g[0][0]=1 $g[i][0]=g[0][i]=g[0][0]=1$ ，也没毛病诶。。
然后就花了我毕生精力找错，各种调试。。最后才知道了问题= =
当Ai≠Bj，并且

f[i][j]=f[i−1][j−1] $f[i][j]=f[i-1][j-1]$ ，
那么根据方案的累计，
g[i-1][j]会累计一次g[i-1][j-1]，
g[i][j-1]会累计一次g[i-1][j-1]，
那么当g[i][j]同时累计上g[i-1][j]和g[i][j-1]时，
明显g[i-1][j-1]重复了诶……
可能你想说就是f[i-1][j]不一定从f[i-1][j-1]转过来，
但是

f[i][j]>=f[i−1][j]>=f[i−1][j−1] $f[i][j]>=f[i-1][j]>=f[i-1][j-1]$ ，f[i][j-1]同理，
所以这个时候一定是都相等的了。

那么Ai=Bj呢？显然啦，f[i][j]=f[i-1][j-1]显然是不可能的。

因此要多加一个判断……如下：

当 A i \neq B j 且 f [i] [j] = f [i - 1] [j - 1] ， g [i] [j] - = g [i - 1] [j - 1]

$当Ai≠Bj且f[i][j]=f[i-1][j-1]，g[i][j]-=g[i-1][j-1]$
接下来注意滚动数组了，内存只有128M。

#include<bits/stdc++.h>
using namespace std;
const int mod=100000000;
char s[5005],s1[5005];
int f[2][5005],g[2][5005];
int main(){scanf("%s",s+1);scanf("%s",s1+1);int n=strlen(s+1)-1,m=strlen(s1+1)-1;g[1][0]=1;for (int j=0;j<=m;j++) g[0][j]=1;for (int i=1;i<=n;i++){int now=i&1,pre=now^1;for (int j=1;j<=m;j++){f[now][j]=max(f[pre][j],f[now][j-1]);if (s[i]==s1[j]){f[now][j]=max(f[now][j],f[pre][j-1]+1);if (f[now][j]==f[pre][j-1]+1) g[now][j]=g[pre][j-1];} else{g[now][j]=0;if (f[now][j]==f[pre][j-1]) g[now][j]=(-g[pre][j-1]+mod)%mod;}if (f[now][j]==f[pre][j]) (g[now][j]+=g[pre][j])%=mod;if (f[now][j]==f[now][j-1]) (g[now][j]+=g[now][j-1])%=mod;}}printf("%d\n%d\n",f[n&1][m],g[n&1][m]);return 0;
}