给定一个序列，每个位置上有一种颜色，要求把这个序列分成可以不连续的若干段，所有颜色相同的要么全部不选要么全部分到一段中，最终选取出的每一段的价值等于段中不同颜色编号的异或和，求最大价值。

题解

一开始我想处理区间之间的嵌套关系和交集关系，然后根据最终区间的嵌套关系来做树形DP，但是处理着处理着我发现区间的嵌套盒交集有一万种关系。

绝望的我选择去翻AC代码，发现了一种新奇的DP思路。

记原序列为 a a ，设 f(i) f(i) 为处理到前 i i 位的最大价值。

f(i) f(i) 可以从两种方式转移来，一种是 f(i)=f(i−1) f(i) = f(i - 1) ，表示 ai a_i 所在的段目前不可选，或不选 ai a_i 颜色所在的段，另一种是考虑合并后的 ai a_i 所在的区间，记其左端点为 j j ，有 。

区间的合并可以在转移 f(i) f(i) 时，从 i i 到 1 1 枚举 j j 的过程中动态转移。注意一种颜色只需要被异或一次。

代码

#include <cstdio>
#include <algorithm>
const int MAX_N = 5000;
int a[MAX_N + 1], l[MAX_N + 1], r[MAX_N + 1], dp[MAX_N + 1], vis[MAX_N + 1];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i <= MAX_N; i++) {
        l[i] = n + 1;
        r[i] = -1;
    }
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        a[i] = x;
        l[x] = std::min(l[x], i);
        r[x] = std::max(r[x], i);
    }
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        int sum = 0, lb = n;
        dp[i] = dp[i - 1];
        for (int j = i; j >= 1; j--) {
            lb = std::min(lb, j);
            int x = a[j];
            if (r[x] > i) break;
            lb = std::min(lb, l[x]);
            if (vis[x] != i) {
                vis[x] = i;
                sum ^= x;
            }
            if (lb == j) {
                dp[i] = std::max(dp[i], dp[j - 1] + sum);
            }
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}