Advertisement
Guest User

Untitled

a guest
May 31st, 2017
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.57 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <algorithm>
  4. #define MAXN 5010
  5.  
  6. using namespace std;
  7.  
  8. int N;
  9. int V[MAXN];
  10.  
  11.  
  12. /// Dove inizia e finisce il segmento contenente l'i-esimo città
  13. int inizio[MAXN];
  14. int fine[MAXN];
  15.  
  16. /// Bellezza di un segmento
  17. long long beauty[MAXN][MAXN];
  18.  
  19. /// Inizio minimo di un segmento che contiene i
  20. int inizio_minimo[MAXN];
  21.  
  22. bool added[MAXN];
  23.  
  24.  
  25. int memo[MAXN];
  26.  
  27. long long dp(int idx) {
  28.     if (idx < 0) return 0;
  29.     if (memo[idx] != -1) {
  30.         return memo[idx];
  31.     }
  32.     long long nope = dp(idx-1);
  33.  
  34.     /// Se questo non è l'ultimo numero
  35.     if (fine[V[idx]] != idx) {
  36.         memo[idx] = nope;
  37.         //printf("dp(%d)[%d] = (no %I64d)\n", V[idx], idx, nope);
  38.         return nope;
  39.     }
  40.  
  41.     long long yep = dp(inizio_minimo[V[idx]]-1)
  42.                         + beauty[inizio_minimo[V[idx]]][idx];
  43.  
  44.     //printf("dp(%d)[%d] = (no %I64d, si %I64d)\n", idx, V[idx], nope, yep);
  45.     memo[idx] = max(nope, yep);
  46.     return memo[idx];
  47. }
  48.  
  49.  
  50.  
  51. int main() {
  52.     //freopen("input.txt", "r", stdin);
  53.  
  54.     scanf("%d", &N);
  55.     for (int i = 0; i < N; i++) scanf("%d", &V[i]);
  56.  
  57.     memset(inizio, -1, sizeof(int) * MAXN);
  58.     for (int i = 0; i < N; i++) {
  59.         memo[i] = -1;
  60.     }
  61.  
  62.     for (int s = 0; s < N; s++) {
  63.         memset(added, 0, sizeof(bool) * MAXN);
  64.  
  65.         if (inizio[V[s]] == -1) {
  66.             inizio[V[s]] = s;
  67.             fine[V[s]] = s;
  68.         }
  69.         else {
  70.             fine[V[s]] = s;
  71.         }
  72.  
  73.         long long b = V[s];
  74.         added[V[s]] = true;
  75.  
  76.         beauty[s][s] = b;
  77.         //printf("\n[%d..%d] = %d\n", s, s, b);
  78.         for (int e = s+1; e < N; e++) {
  79.             /// Se in questo segmento non c'è questa città
  80.             /// Fai lo xor
  81.             if (!added[V[e]]) {
  82.                 b ^= V[e];
  83.                 added[V[e]] = true;
  84.             }
  85.             beauty[s][e] = b;
  86.             //printf("[%d..%d] = %d\n", s, e, b);
  87.         }
  88.     }
  89.     for (int i = 0; i < MAXN; i++) {
  90.         if (inizio[i] == -1) continue;
  91.         //printf("Segmento %d va da %d a %d\n", i, inizio[i], fine[i]);
  92.         int imin = MAXN;
  93.         for (int j = inizio[i]; j <= fine[i]; j++) {
  94.             imin = min(imin, inizio[V[j]]);
  95.         }
  96.         //printf("inizio minimo segmento %d = %d\n\n", i, inizio_minimo);
  97.         inizio_minimo[i] = imin;
  98.     }
  99.  
  100.     for (int i = 0; i < MAXN; i++) {
  101.  
  102.         //printf("inizio(%d) = %d, inizio_minimo = %d\n", i, inizio[i], inizio_minimo[i]);
  103.     }
  104.  
  105.  
  106.     long long ris = dp(N-1);
  107.     printf("%I64d\n", ris);
  108.  
  109.     return 0;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement