#416 Div2 C

#416 Div2 C

题意

一些人去坐车，它们已经按给定顺序排队，每个人可能去不同的目的地，去同一目的地的人一定要被分成一组（去不同目的地的也可被分到同一组），对分好的每一组所有不同的目的地序号作异或，并求和，求使得结果最大。（不要求每个人都要分组，不能改变人的顺序，在同一组的人序号必须连续）

分析

首先预处理找到以每个人为左端可以产生的分组（显然有些人不能作为左端，如果可以，那么一定是唯一确定的分组），然后记忆化搜索一下即可。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e3 + 10;

int a[MAXN];

int b[MAXN];

int bl[MAXN], br[MAXN];

int xora[MAXN];

int n;

int dp[MAXN];

void dfs(int x, int res) {

    if(res <= dp[x]) return;

    else dp[x] = res;

    if(x >= n) return;

    if(x == bl[a[x]]) dfs(br[a[x]] + 1, res + xora[bl[a[x]]]);

    dfs(x + 1, res);

}

int main() {

    cin >> n;

    memset(dp, -1, sizeof dp);

    for(int i = 0; i < n; i++) {

        scanf("%d", &a[i]);

        if(!b[a[i]]) bl[a[i]] = i;

        b[a[i]]++;

        br[a[i]] = i;

    }

    for(int i = 0; i < 5001; i++) {

        set<int> s;

        if(!b[i]) continue;

        for(int j = bl[i]; j <= br[i]; j++) {

            br[i] = max(br[i], br[a[j]]);

            if(bl[a[j]] < bl[i]) {

                bl[i] = bl[a[j]];

            }

        }

        if(a[bl[i]] != i) continue;

        for(int j = bl[i]; j <= br[i]; j++) {

            if(!s.count(a[j])) {

                s.insert(a[j]);

                xora[bl[i]] ^= a[j];

            }

        }

    }

    dfs(0, 0);

    cout << dp[n] << endl;

    return 0;

}