Vladik and Memorable Trip 【CodeForces - 811C】【DP】

题目链接

题目大意

题意有点难读，有点绕：
就是有一个长度为n的序列，要把这个序列分成若干个子串，然后挑选几个子串让他们的异或和最大，相同的数字必须早同一个子串里

解题思路

比赛的时候就知道是个DP，奈何DP差的不忍直视
dp[i]就是1到i直接的子串异或和最大值
每次枚举新加的数可以组成的新的子串更新答案

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

const int N=5005;
struct node
{
    int s,e;
};
node a[N];
int dp[N],e[N],vis[N];

int main()
{
    memset(a,0,sizeof(a));
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&e[i]);
        if(a[e[i]].s==0)
            a[e[i]].s=i;
        a[e[i]].e=i;
    }
    for(int i=1; i<=n; i++)
    {
        dp[i]=dp[i-1];
        memset(vis,0,sizeof(vis));
        int ans=0;
        int w=i;
        for(int j=i; j>=1; j--)
        {
            int v=e[j];
            if(vis[v]==0)
            {
                if(a[v].e>i)
                    break;
                w=min(a[v].s,w);
                ans=ans^v;
                vis[v]=1;
            }
            if(j<=w)
                dp[i]=max(dp[i],dp[j-1]+ans);
        }
    }
    printf("%d\n",dp[n]);
    return 0;
}