题目描述

难度分:$1739$

输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 20)$。

输出$a$的子序列$b$的最长长度，满足：

1. $b$的长度是偶数。
2. $b[0]=b[1]$，$b[2]=b[3]$，……即两个两个一组，每组中的元素都相同。
3. $b$中的每种数字恰好在$b$中出现两次。

注：子序列不一定连续。

输入样例$1$

7
1 3 3 1 2 2 1

输出样例$1$

4

输入样例$2$

1
20

输出样例$2$

0

算法

状压DP

这个题的值域非常小，比较容易想到状压DP，但是$2^{20}$已经很大了，如果状态再加上下标的话就会有$O(2^{20}n)$的状态，是不可能存下来的。

状态定义

$dp[mask]$表示状态$mask$达成时，这个模式最后一个数字在原数组中的最左索引。因为对于同一个模式，越靠左越能为后面腾出更多位置，让后面有可能接更多元素。先将$a$数组中的所有元素都减去$1$，$mask$中第$i$位是$1$就表示数子$i$存在于子序列中。如果$S$是所有可以达成的状态集合，那么答案就是$max_{mask \in S}popcount(mask) \times 2$，其中$popcount(x)$表示二进制数字$x$中$1$的个数。

状态转移

首先$dp[0]=0$，表示空序列的最后一个位置是索引$0$。那么对于一个状态$mask$，我们考虑接下来将不存在于$mask$中的数字$v \in [0,M]$加入到序列末尾，其中$M$位最大值。

先得到$mask$状态最后一位$i=dp[mask]$，然后找$i$右边最近的$v$，假设在$j=R[i][v]$位置，如果$j=R[i][v] \leq n$，且$k=R[R[i][v]][v] \leq v$，说明模式$mask$后面可以找到两个$v$，$v$可以接在模式$mask$的后面。

其中$R[i][v]$表示$i$右边最近的$v$，可以倒序遍历一遍$a$直接预处理出来。然后我们维护$dp[mask \lor 2^{v}]=min(dp[mask \lor 2^{v}],k)$的最小值即可，如果$mask$可以达成，就维护$popcount(mask) \times 2$的最大值。

复杂度分析

时间复杂度

遍历一遍数组$a$，对每个$i$，遍历$v \in [0,m]$就能处理出$R$数组，时间复杂度为$O(nm)$。遍历所有状态$mask$的时间复杂度为$O(2^{m})$，对于每个状态，需要枚举接在后面的数字$v$，时间复杂度为$O(m)$，本题中$m=20$，所以DP的时间复杂度为$O(m2^m)$。整个算法的时间复杂度为$O(m(n+2^m))$。

空间复杂度

空间瓶颈在于$R$数组和DP数组，两者的空间复杂度分别为$O(nm)$和$O(2^m)$，整个算法的额外空间复杂度为$O(nm+2^m)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010, M = 20;
int n, a[N], dp[(1<<M) + 5], nxt[M], R[N][M];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        a[i]--;
    }
    memset(nxt, 0x3f, sizeof nxt);
    for(int i = n; i >= 0; i--) {
        for(int v = 0; v < M; v++) {
            R[i][v] = nxt[v];    // i右边最近的v在哪个索引
        }
        nxt[a[i]] = i;
    }
    int ans = 0;
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    int cnt = 0;
    for(int mask = 0; mask < (1<<M); mask++) {
        int i = dp[mask];
        if(i > n) continue;   // 这个状态达成不了
        for(int v = 0; v < M; v++) {
            if(mask>>v&1) continue;
            int j = R[i][v];
            if(j > n) continue;
            int k = R[j][v];
            if(k <= n) {
                dp[mask|(1<<v)] = min(dp[mask|(1<<v)], k);
            }
        }
        ans = max(ans, __builtin_popcount(mask)<<1);
    }
    printf("%d\n", ans);
    return 0;
}