Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <string.h>
- #include <algorithm>
- #define MAXN 5010
- using namespace std;
- int N;
- int V[MAXN];
- /// Dove inizia e finisce il segmento contenente l'i-esimo città
- int inizio[MAXN];
- int fine[MAXN];
- /// Bellezza di un segmento
- long long beauty[MAXN][MAXN];
- /// Inizio minimo di un segmento che contiene i
- int inizio_minimo[MAXN];
- bool added[MAXN];
- int memo[MAXN];
- long long dp(int idx) {
- if (idx < 0) return 0;
- if (memo[idx] != -1) {
- return memo[idx];
- }
- long long nope = dp(idx-1);
- /// Se questo non è l'ultimo numero
- if (fine[V[idx]] != idx) {
- memo[idx] = nope;
- //printf("dp(%d)[%d] = (no %I64d)\n", V[idx], idx, nope);
- return nope;
- }
- long long yep = dp(inizio_minimo[V[idx]]-1)
- + beauty[inizio_minimo[V[idx]]][idx];
- //printf("dp(%d)[%d] = (no %I64d, si %I64d)\n", idx, V[idx], nope, yep);
- memo[idx] = max(nope, yep);
- return memo[idx];
- }
- int main() {
- //freopen("input.txt", "r", stdin);
- scanf("%d", &N);
- for (int i = 0; i < N; i++) scanf("%d", &V[i]);
- memset(inizio, -1, sizeof(int) * MAXN);
- for (int i = 0; i < N; i++) {
- memo[i] = -1;
- }
- for (int s = 0; s < N; s++) {
- memset(added, 0, sizeof(bool) * MAXN);
- if (inizio[V[s]] == -1) {
- inizio[V[s]] = s;
- fine[V[s]] = s;
- }
- else {
- fine[V[s]] = s;
- }
- long long b = V[s];
- added[V[s]] = true;
- beauty[s][s] = b;
- //printf("\n[%d..%d] = %d\n", s, s, b);
- for (int e = s+1; e < N; e++) {
- /// Se in questo segmento non c'è questa città
- /// Fai lo xor
- if (!added[V[e]]) {
- b ^= V[e];
- added[V[e]] = true;
- }
- beauty[s][e] = b;
- //printf("[%d..%d] = %d\n", s, e, b);
- }
- }
- for (int i = 0; i < MAXN; i++) {
- if (inizio[i] == -1) continue;
- //printf("Segmento %d va da %d a %d\n", i, inizio[i], fine[i]);
- int imin = MAXN;
- for (int j = inizio[i]; j <= fine[i]; j++) {
- imin = min(imin, inizio[V[j]]);
- }
- //printf("inizio minimo segmento %d = %d\n\n", i, inizio_minimo);
- inizio_minimo[i] = imin;
- }
- for (int i = 0; i < MAXN; i++) {
- //printf("inizio(%d) = %d, inizio_minimo = %d\n", i, inizio[i], inizio_minimo[i]);
- }
- long long ris = dp(N-1);
- printf("%I64d\n", ris);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement