题解：CF811C Vladik and Memorable Trip

lgx57 · 2024-12-15 14:13:17 · 题解

非常简单的 dp。

只需要暴力枚举每一个区间，然后判断合法后直接转移即可。

但是普通的判断合法会 TLE，需要预处理出每一个数在整个数组里的出现次数，然后把一个区间里的数全部插入到 set 中，遍历 set，如果在区间中出现次数等于整个数组中的出现次数，那么下次就不用判断，直接 erase，否则这个区间是不合法的。

另外注意没有区间可以转移时 dp_i \gets dp_{i-1}。

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=n;i++) num[a[i]]++,ma=max(ma,a[i]);
    for (int i=1;i<=n;i++){
        for (int _=0;_<=ma;_++) cnt[_]=0;
        int sum=0;
        set<int> s;
        for (int j=i;j>=1;j--){
            bool f=1;
            if (!cnt[a[j]]) sum^=a[j],s.insert(a[j]);
            cnt[a[j]]++;
            vector<int> v;
            for (int x:s){
                if (cnt[x]!=num[x]){
                    f=0;//不合法
                    break;
                }
                else v.pb(x);
            }
            for (int x:v) s.erase(x);//下次不需要判断
            if (f) dp[i]=max(dp[j-1]+sum,dp[i]);//直接转移
        }
        dp[i]=max(dp[i],dp[i-1]);//没有区间可以转移
    }
    cout<<dp[n];
    return 0;
}