题解 | #小苯的序列涂色#

线性dp问题，我们可以设置dp[i]数组表示到第i个位置的最小值，最后dp[n]即为答案，首先我们可以求出前缀异或和p[N]，根据异或和的运算性质可知，a^b^b=a,因此j到i区间的异或和为p[i]^p[j-1]，这个就是染色j-i所需要的代价。n的范围5e3，因此我们可以考虑n²的复杂度，双重循环枚举dp[i]，外层枚举1-i，内侧枚举0-j，因为可以重复染色所以我们可以设置参数mn记录j到i中最小的p[i]^p[j-1]让后面的j使用，状态转移方程即为dp[i]=min(dp[i]+dp[j]+mn)。

```#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
const long long INF = (long long)4e18;

long long a[N], p[N], dp[N];

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        p[0] = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            p[i] = p[i - 1] ^ a[i];
        }
        for (int i = 0; i <= n; i++) dp[i] = INF;//初始化
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            long long mn = INF;
            for (int j = 0; j < i; j++) {
                mn = min(mn,p[i] ^ p[j]);//因为区间可以重复染色 所以可以保存j小的时候的
                dp[i] = min(dp[i], dp[j] + mn);
            }
        }

        cout << dp[n] << '\n';
    }
    return 0;
}