E 拼接串

题目描述

给出一个长度为 \(n\) 的正整数串 \(a\) 。现在可以把两个没有重叠的连续子串前后拼接起来，但是要求拼接之后的数串中每个正整数不能出现超过 \(1\) 次。请问能拼接出来的符合要求的数字串的最大长度是多少。

输入描述

第一行一个整数 \(n\) \((1 \leq n \leq 1,000,000)\)，代表序列 \(a\) 的长度。

第二行为 \(n\) 个用空格隔开的正整数 \(a_i\) \((1 \leq a_i \leq 18)\)。

输出描述

一行一个整数，代表符合要求的拼接后数字串的最长长度。

解题思路

观察数据范围可以发现 \(1 \leq a \leq 18\)，这是一个重要的突破口，可以考虑使用状压DP枚举子集对所有的状态进行枚举和转移。

代码实现

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int n, mask = 1 << 18, ans = 0;  // mask是总状态数
    std::cin >> n;

    std::vector<int> a(n + 1), dp((1 << 18) + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        // i是起始位置，j是终止位置
        for (int j = i, s = 0; j <= n; j++) {  // s记录子串是不是出现了某个数字
            if (s >> (a[j] - 1) & 1) {  // 判断子串是否包含了a[j]
                break;
            }
            s |= 1 << (a[j] - 1);  // 记录这个数字
            dp[s] = std::max(dp[s], j - i + 1);  // 更新出现这几个数字时的最大值
            ans = std::max(ans, dp[s]);
        }
    }

    for (int i = 0; i < mask; i++) {  // 枚举所有的状态
        // 一种位运算的技巧，效果类似不断右移直到最低位是1再进行计算，此处是在不断枚举i的非空子集
        for (int j = i; j > 0; j = i & (j - 1)) {
            // 异或的性质可以保证i^j和j在二进制下不会有重合的数字，遍历更新最大值即可
            ans = std::max(ans, dp[i ^ j] + dp[j]);
        }
    }

    std::cout << ans;
}