P12738 [POI 2016 R2] 口吃 Stutter
Iceturky
·
·
题解
Link
给定两个序列，求满足 \forall i,p_{2i-1}=p_{2_i} 的 LCS。
首先有基础的 \mathrm{O(n^2)} dp。
其中 $frm$ 数组是对应序列内上一个相同颜色的元素下标。
可以发现这个数组的差分（$f_{i,j}-f_{i,j-1}$）只有 $0$ 或 $1$。
用 bitset 存储，前两个转移可以直接滚，第三个在用到的时候用差分数组加载即可。
（校内互测搬了这题，空间限制开了 20M，可以通过删除只出现了一次的元素以及只对不同颜色存储差分数组对空间使用除 $2$）
是有点暴力邪道的做法。
code
```cpp
const int N=1.5e4+5;
bitset<N>f[N];
int g[N],h[N];
int a[N],b[N];
int lsa[N],lsb[N];
unordered_map<int,int>id;
signed main(){
int n=read(),m=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=m;i++)
b[i]=read();
for(int i=1;i<=n;i++){
lsa[i]=id[a[i]];
id[a[i]]=i;
}id.clear();
for(int i=1;i<=m;i++){
lsb[i]=id[b[i]];
id[b[i]]=i;
}
for(int i=1;i<=n;i++){
if(lsa[i]){
for(int j=1;j<=m;j++)
h[j]=h[j-1]+f[lsa[i]-1][j];
}
for(int j=1;j<=m;j++){
g[j]=max(g[j-1],g[j]);
if(a[i]==b[j]&&lsa[i]&&lsb[j])
g[j]=max(g[j],h[lsb[j]-1]+1);
f[i][j]=g[j]-g[j-1];
}
}print(g[m]*2),pc('\n');
return 0;
}
```