P12738 题解

· · 题解

题意

给定两个序列 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;
}