cf811C(预处理&dp)

题目链接: http://codeforces.com/problemset/problem/811/C

题意: 给一个有n个人排队上车，去相同地方的人要么坐在同一个车厢，要不就不上车，问最大舒适度和是多少。苏适度是车厢内所有数组成的集合的异或值。

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

注意: 相交的区间要么全选要么全不选

思路: dp

dp[i] 存储前 i (即 i 为元素 a[i] 所在区间的右边界)个人最大舒适度值, 对于当前 i , 从 i 往前更新一遍.

动态转移方程式为: dp[i] = max(dp[i], dp[j] + ans) , 其中 ans 为合法区间 [j, i] 的舒适度.

需要先预处理一下 a[i] 所在区间来判断选取区间时的合法性.

代码:

#include <iostream>
#include <stdio.h>
using namespace std;

const int MAXN = 5e3 + 10;
int s[MAXN], e[MAXN], a[MAXN], dp[MAXN];

int main(void){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        if(!s[a[i]]) s[a[i]] = i;
        e[a[i]] = i;
    }
    for(int i = 1; i <= n; i++){
        dp[i] = dp[i -1];
        int vis[MAXN] = {0,};
        int cnt = s[a[i]], ans = 0;
        for(int j = i; j > 0; j--){
            if(!vis[a[j]]){
                if(e[a[j]] > i) break;
                cnt = min(cnt, s[a[j]]);
                ans ^= a[j];
                vis[a[j]] = 1;
            }
            if(j == cnt) dp[i] = max(dp[i], dp[j - 1] + ans);
        }
    }
    printf("%d
", dp[n]);
    return 0;
}