题解：P11187 配对序列

· · 题解

D. 配对序列 (pairing) 官方题解

本题考查的主要知识点有：

送分

读题后不难发现测试点 10 的输出为 0。

对于测试点 11，一个数可以出现在答案中当且仅当该数字出现了 2 次。所以统计出现至少两次的数字种数再乘以 2 即可。

前 2 个测试点可以直接枚举子序列，然后判断是否符合题意，时间复杂度 O(n2^n)。

如果考场上没有任何思路，那么这 20 分可以尝试拿到手。

朴素的 DP

题目也是让你求某种子序列的个数，类似求最长上升子序列，我们考虑 DP。

令 f(i) 为以 i 结尾的最长配对子序列的长度，则每次转移要枚举 i 的上一个数的位置 j 和上上个数的位置 k，如果 a_i=a_j 且 a_j\ne a_k，那么 f_i 可以变成 \max(f_i, f_k+2)。该方法时间复杂度为 O(n^3)，可以通过测试点 1\sim 5 拿到 25 分，如果结合送分，可得 35 分。

我们发现时间复杂度瓶颈在于每次转移需要枚举两个数。如果我们能把长度为奇数的子序列也写进某种 DP 里，那么每次转移只要枚举上一个数的位置。

令 even(i) 表示以 i 结尾的最长配对子序列长度，odd(i) 表示以 i 结尾，除了长度是奇数以外都满足配对子序列的要求的、最长子序列长度。

转移 even(i) 时，枚举所有 j<i，如果 a_j=a_i，那么用 odd(j)+1 去更新 even(i)。

转移 odd(i) 时，枚举所有 j<i，如果 a_j\ne a_i，那么用 even(j)+1 去更新 odd(i)。

时间复杂度 O(n^2)，可得 45 分，结合送分可得 55 分。

更优秀的 DP

经过观察，发现如果 a_i=a_j，且 i<j，那么 j 处的 DP 值一定大于 i 处的 DP 值（因为 j 的转移范围大于 i 的转移范围）。因此转移 even(i) 时，我们只需要找到 i 之前最近的和 a_i 相等的 a_j 进行转移。实现上，在 i 从前往后扫描的过程中，用 pre_v 来记录 a 中上一次出现数 v 的位置即可。

对于 odd(i)，如果是测试点 12\sim 14，那么只需要在 i 从前往后循环的同时记录下 even(i) 的最大值即可——毕竟因为所有数最多出现 2 次，如果 a_ i 是第一次出现，那么 i 之前的 j 都有 a_j\ne a_i；而如果 a_i 是第二次出现，这个 odd(i) 就不可能再被某种 even(j) 调用，正确性也就不重要了。

然而对于所有测试点，只记录 even(i) 最大值（记为 even(J)）是不够的——如果 a_i=a_J，那么这时就要转而求“次大值”。总而言之，我们需要在 i 从前往后循环的同时，记录 a_J 不同的 even(J) 前二大。

这样，总时间复杂度就是 O(n+\max a_i) 的了，可以通过。

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,a[N],even[N],odd[N],pre[N];
int main(){
    scanf("%d",&n);
    int b1=0,b2=0;
    odd[0]=-1e9;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[b1]==a[i])
            odd[i]=even[b2]+1;
        else odd[i]=even[b1]+1;
        even[i]=odd[pre[a[i]]]+1;
        if(even[i]>=even[b1]){
            if(a[i]!=a[b1])
                b2=b1;
            b1=i;
        }
        else if(even[i]>=even[b2] && a[i]!=a[b1])
            b2=i;
        pre[a[i]]=i;
    }
    printf("%d\n",even[b1]);
    return 0;
}