本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-18 16:38:03

题意

给定两个序列 $a,b$，求其最长合法公共子序列长度。序列 $s$ 合法当且仅当其长度 $k$ 为偶数，且 $\forall 1\le i\le \frac k2,s_{2i}=s_{2i-1}$。$n,m\le 15000$，空间限制 $32$ MB。

题解

由于有相同限制，直接一对一对选择。注意到若 $i<j<k$ 且 $a_i=a_j=a_k$，一定不会选择 $i,k$ 配对，因为将其调整为 $i,j$ 或 $j,k$ 一定不劣。所以匹配位置之间不会有相同元素，即 $i$ 只可能与 $a_i$ 上次出现位置 $pre_i$ 或下次出现位置 $nxt_i$ 配对，两个数组的 $pre$ 和 $nxt$ 均可以扫一遍预处理。

据此显然有时空 $O(n^2)$ 的 DP，设 $f_{i,j}$ 表示两个序列分别用前 $i,j$ 个元素时，可匹配的最大对数。转移首先有 $f_{i,j}\rightarrow f_{i+1,j}$ 和 $f_{i,j}\rightarrow f_{i,j+1}$，另外当 $a_i=b_j$ 时有 $f_{i,j}+1\rightarrow f_{nxt_i,nxt'_j}$。然而开不下 $O(n^2)$ 空间的数组，这也难以滚动数组优化，需要修改状态。

由于 DP 值也是 $O(n)$ 级别的，考虑换维处理，改为设 $f_{x,i}$ 表示选了 $x$ 对且 $a$ 序列用到 $i$ 位置时，$b$ 序列至少要用到 $f_{x,i}$ 位置。这样 $x$ 一维只会从 $x-1$ 转移过来，可以滚动数组优化掉，问题在于如何转移。首先有 $f_{x,i}\leftarrow f_{x,i-1}$，然后若使用 $a_i=b_j$ 需要 $f_{x-1,i-1} \lt j$，此时有转移 $f_{x,nxt_i}\leftarrow nxt'_j$。

显然 $f_{x-1}$ 是单调不增的，因此枚举的 $i$ 递增时，合法 $j$ 的后缀左端点也是不增的。因此依次从后往前加入 $j$，并对每种值 $t$ 维护 $g_t$，表示目前合法且 $b_j=t$ 的 $nxt'j$ 最小值，之后试图用 $g{a_i}$ 更新 $f_{x,nxt_i}$ 即可。时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。由于答案不超过 $\lfloor\frac {\min(n,m)} 2\rfloor$，且只需要做答案轮 DP 转移，在写题解时是最优解。

代码

#include<iostream>
#include<algorithm>
#define lb lower_bound
using namespace std;
const int N=1.5e4+10;
int n,m,k,a[N],b[N],na[N],nb[N],pre[N<<1],c[N<<1],f[2][N],g[N<<1];
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i],c[++k]=a[i];
	for(int i=1;i<=m;i++) cin>>b[i],c[++k]=b[i];
	sort(c+1,c+1+k),k=unique(c+1,c+1+k)-c-1;
	for(int i=1;i<=n;i++) a[i]=lb(c+1,c+1+k,a[i])-c;
	for(int i=1;i<=m;i++) b[i]=lb(c+1,c+1+k,b[i])-c;
	for(int i=n;i;i--) na[i]=pre[a[i]],pre[a[i]]=i;
	for(int i=1;i<=k;i++) pre[i]=0;
	for(int i=m;i;i--) nb[i]=pre[b[i]],pre[b[i]]=i;
	for(int x=1;;x++)
	{
		int cur=(x&1),last=1-cur,j=m;
		for(int i=0;i<=n;i++) f[cur][i]=N;
		for(int t=1;t<=k;t++) g[t]=N;
		for(int i=1;i<=n;i++)
		{
			while(f[last][i-1]<j&&j)
			{
				if(nb[j]) g[b[j]]=min(g[b[j]],nb[j]);
				j--;
			}
			if(na[i]) f[cur][na[i]]=min(f[cur][na[i]],g[a[i]]);
			f[cur][i]=min(f[cur][i],f[cur][i-1]);
		}
		if(f[cur][n]==N) {cout<<x*2-2; break;}
	}
	return 0;
}