Codeforces 811C Vladik and Memorable Trip (区间异或最大值) (线性DP)

<题目链接>

题目大意：

给你n个数，现在让你选一些区间出来，对于每个区间中的每一种数，全部都只能出现在这个区间。 每个区间的价值为该区间不同的数的异或值之和，现在问你这n个数最大的价值是多少。

解题分析：
因为要同一种的所有数只能出现在同一区间，所以我们先对这$n$个数进行预处理，得到他们每种数的最左边的坐标和最右边的坐标。因为数据只有5000，所以状态可以比较暴力地更新，枚举最后一个异或的区间进行更新，用dp值来记录。

$dp[i]$表示$[1,i]$中异或值之和的最大值。第$i$个可以选或者不选，从这两种情况中选最大值。

不难想到，我们暴力枚举最后一个异或的区间，设区间左端点为$j$，区间端点为$i$。

转移方程就是：$dp[i]=max(dp[i],dp[j-1]+res)$    res表示$[j,i]$区间所有数的异或值

#include <bits/stdc++.h>
using namespace std;

const int N = 5e3+5;
int L[N],R[N];
int arr[N],dp[N],vis[N];

int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);
        if(!L[arr[i]])L[arr[i]]=i;   
        R[arr[i]]=i;      
    }
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1];     //首先默认不选这个数
        memset(vis,0,sizeof(vis));
        int res=0,le=1e9,ri=-1;
        for(int j=i;j>=1;j--){     //枚举的区间左端点
            le=min(le,L[arr[j]]);ri=max(ri,R[arr[j]]);
            if(!vis[arr[j]])
                res^=arr[j],vis[arr[j]]++;
            if( ri>i || le<j )continue;    //如果这个区间存在不符合要求的点，就不对该区间左端点的状态进行转移
            dp[i]=max(dp[i],dp[j-1]+res);    
        }
    }
    cout<<dp[n]<<endl;
}