题解 P2543 【[AHOI2004]奇怪的字符串】
Mars_Dingdang
2020-10-31 17:45:01
本题为 LCS 模板，且数据范围允许 $O(n^2)$ 算法。本文后面会介绍进阶版本。
## 题目大意
求 $\operatorname{Longest\ Common\ Subsequence}(A,B)$。
## 大体思路
首先介绍 $O(n^2)$ 算法。
用 $f(i,j)$ 表示 $\operatorname{Lcs}A[1\sim i],B[1\sim j]$。分三种情况：
1. 若选择 $A_i$ 但不选 $B_j$，则 $f(i,j)=\max\left\{f_{(i,j)},f_{(i,j-1)}\right\}$；
1. 若选择 $B_j$ 但不选 $A_i$，则 $f(i,j)=\max\left\{f_{(i,j)},f_{(i-1,j)}\right\}$；
3. 当 $A_i=B_j$ 时，两个元素均选择，此时 $f(i,j)=\max\left\{f_{(i,j)},f_{(i-1,j-1)}+1\right\}$。
由于每一次状态转移均只需用到 $i-1$，因此用滚动数组优化空间。
代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int Max(int x,int y) {return x>y?x:y;}//手写会快一点
const int maxn=10005;
int f[2][maxn],n,m;
char a[maxn],b[maxn];
int main(){
scanf("%s",a+1);n=strlen(a+1);
scanf("%s",b+1);m=strlen(b+1);//输入
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i&1][j]=Max(f[i&1][j-1],f[(i-1)&1][j]);//滚动数组优化
if(a[i]==b[j]) f[i&1][j]=Max(f[i&1][j],f[(i-1)&1][j-1]+1);
}//ab 均选
}
printf("%d",f[n&1][m]);//输出
return 0;
}
```
~~（抄代码的可以走了）~~
## 优化
要想压缩时间效率，关键就在 $for$ 循环上，做到尽可能少的遍历即可
1. 首先我们给第一个序列的值进行按顺序的编号，即将 $a$ 数组 $\{11\ 77\ 55\ 44\ 88\ 33\ 99\}$ 变为 $\{11\ 22\ 33\ 44\ 55\ 66\ 77\}$，并开一个数组将修改的值标记。
2. 对另一个序列，进行同样的编号，即根据开的标记数组赋值（同一个编号对应的值相同，若 $b$ 数组中含有 $a$ 中没有的值，就编号为 $0$ ,因为后续操作无须考虑）。
3. 这时，公共子序列就是 $b$ 中编号上升的序列，为什么？因为你进行编号就是为了便于判断顺序，肯定是要编号小的在前才能形成公共子序列，即顺序和 $a$ 中一致。
4. 最后一步，二分查找 $b$ 中最大上升子序列，用 $\text{lower\_bound}$，效率更高。
于是，复杂度降为 $O(n\log n)$。
例题：https://www.luogu.com.cn/problem/UVA10635 。
## 求次数
那究竟如何求 LCS 出现的次数呢？其实还是用动态规划的思想，加上简单的容斥。
考虑 $f[i][j]=k$,那么就加上 $f[i-1][j]$ 和 $f[i][j-1]$ 中 $=k$ 的方案数。
如果 $a[i]=b[j]$ ,那么还要算上 $f[i-1][j-1]$ 的方案数；但是如果 $a[i]\neq b[j]$ 且 $f[i-1][j-1]=k$，就要减去它的方案数了（容斥）。
另外，一定要开滚动数组（一次只存两状态即可），否则 MLE 等着你。
代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5005;
const int mod=1e8;
int f[2][maxn],g[2][maxn],n,m;
char a[maxn],b[maxn];
signed main(){
scanf("%s",a+1);scanf("%s",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++){
for(int j=1;j<=m;j++){
f[i&1][j] = max(f[(i-1)&1][j],f[i&1][j-1]);
g[i&1][j] = 0;
if(a[i] == b[j]) f[i&1][j] = max(f[i&1][j],f[(i-1)&1][j-1]+1);
if(a[i] == b[j] && f[i&1][j] == f[(i-1)&1][j-1]+1)
g[i&1][j] += g[(i-1)&1][j-1];
if(f[(i-1)&1][j] == f[i&1][j])
g[i&1][j] += g[(i-1)&1][j];
if(f[i&1][j-1] == f[i&1][j])
g[i&1][j] += g[i&1][j-1];
if(f[i&1][j] == f[(i-1)&1][j-1])
g[i&1][j] -= g[(i-1)&1][j-1];
(g[i&1][j]+=mod) %= mod;
}
}
printf("%lld\n%lld",f[n&1][m],g[n&1][m]);
return 0;
}
```
例题：https://www.luogu.com.cn/problem/P2516 。