<题目链接>
题目大意：
给你n个数，现在让你选一些区间出来，对于每个区间中的每一种数，全部都只能出现在这个区间。 每个区间的价值为该区间不同的数的异或值之和，现在问你这n个数最大的价值是多少。
解题分析：
刚开始真的是没有什么想法。因为要同一种的所有数只能出现在同一区间，所以我们先对这$n$个数进行预处理，得到他们每种数的最左边的坐标和最右边的坐标。然后就是暴力枚举最后一个异或的区间进行更新，用dp值来记录。
$dp[i]$表示$[1,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 n,L[N],R[N]; int arr[N],dp[N],vis[N]; int main(){ 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]; //首先默认这个数不取 if(R[arr[i]]==i){ //如果这个点是最右边的数 memset(vis,0,sizeof(vis)); int res=0; bool fp=true; for(int j=L[arr[i]];j<=i;j++){ //这个区间的所有不相等的数的异或值 if(R[arr[j]]>i || L[arr[j]]<L[arr[i]]){ fp=false; break; } if(!vis[arr[j]]) res^=arr[j],vis[arr[j]]++; } if(fp)dp[i]=max(dp[i],dp[L[arr[i]]-1]+res); } //WA 29的写法 }*/ for(int i=1;i<=n;i++){ dp[i]=dp[i-1]; memset(vis,0,sizeof(vis)); int res=0,left=i; for(int j=i;j>=1;j--){ //枚举的区间左端点 if(!vis[arr[j]]){ //枚举1~i区间的所有点 if(R[arr[j]]>i)break; left=min(left,L[arr[j]]); //得到这个区间内所有元素的最左边的端点坐标 res^=arr[j]; vis[arr[j]]++; } if(left>=j)dp[i]=max(dp[i],dp[j-1]+res); //如果大于枚举的区间左值，则成立 } } cout<<dp[n]<<endl; }
Codeforces 811C Vladik and Memorable Trip (区间异或最大值)【线性DP】
原文：https://www.cnblogs.com/00isok/p/10673944.html