Advertisement
Guest User

Untitled

a guest
May 31st, 2017
46
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.81 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. int fine_massima[MAXN];
  22.  
  23. bool added[MAXN];
  24.  
  25.  
  26. int memo[MAXN];
  27.  
  28. long long dp(int idx) {
  29.     if (idx < 0) return 0;
  30.     if (memo[idx] != -1) {
  31.         return memo[idx];
  32.     }
  33.     long long nope = dp(idx-1);
  34.  
  35.     /// Se questo non è l'ultimo numero
  36.     if (fine[V[idx]] != idx) {
  37.         memo[idx] = nope;
  38.         //printf("dp(%d)[%d] = (no %I64d)\n", V[idx], idx, nope);
  39.         return nope;
  40.     }
  41.  
  42.     int s = inizio_minimo[V[idx]];
  43.     int e = idx;
  44.  
  45.     bool possible = true;
  46.     for (int i = s; i <= e && possible; i++) {
  47.         if (V[i] == idx) continue;
  48.         if (fine[V[i]] > idx) possible = false;
  49.     }
  50.     if (!possible) {
  51.         memo[idx] = nope;
  52.         return nope;
  53.     }
  54.     long long yep = dp(s-1) + beauty[s][e];
  55.  
  56.     //printf("dp(%d)[%d] = (no %I64d, si %I64d)\n", idx, V[idx], nope, yep);
  57.     memo[idx] = max(nope, yep);
  58.     return memo[idx];
  59. }
  60.  
  61.  
  62.  
  63. int main() {
  64.     //freopen("input.txt", "r", stdin);
  65.  
  66.     scanf("%d", &N);
  67.     for (int i = 0; i < N; i++) scanf("%d", &V[i]);
  68.  
  69.     memset(inizio, -1, sizeof(int) * MAXN);
  70.     for (int i = 0; i < N; i++) {
  71.         memo[i] = -1;
  72.     }
  73.  
  74.     for (int s = 0; s < N; s++) {
  75.         if (inizio[V[s]] == -1) {
  76.             inizio[V[s]] = s;
  77.             fine[V[s]] = s;
  78.         }
  79.         else {
  80.             fine[V[s]] = s;
  81.         }
  82.     }
  83.  
  84.     for (int s = 0; s < N; s++) {
  85.         memset(added, 0, sizeof(bool) * MAXN);
  86.  
  87.         long long b = V[s];
  88.         added[V[s]] = true;
  89.  
  90.         beauty[s][s] = b;
  91.         //printf("\n[%d..%d] = %d\n", s, s, b);
  92.         for (int e = s+1; e < N; e++) {
  93.             /// Se in questo segmento non c'è questa città
  94.             /// Fai lo xor
  95.             if (!added[V[e]]) {
  96.                 b ^= V[e];
  97.                 added[V[e]] = true;
  98.             }
  99.             beauty[s][e] = b;
  100.             //printf("[%d..%d] = %d\n", s, e, b);
  101.         }
  102.     }
  103.     for (int i = 0; i < MAXN; i++) {
  104.         if (inizio[i] == -1) continue;
  105.         int imin = MAXN;
  106.         int fmax = -1;
  107.         for (int j = inizio[i]; j <= fine[i]; j++) {
  108.             imin = min(imin, inizio[V[j]]);
  109.             fmax = max(fmax, fine[V[j]]);
  110.         }
  111.         inizio_minimo[i] = imin;
  112.         fine_massima[i] = fmax;
  113.     }
  114.  
  115.     for (int i = 0; i < MAXN; i++) {
  116.  
  117.         //printf("inizio(%d) = %d, inizio_minimo = %d\n", i, inizio[i], inizio_minimo[i]);
  118.     }
  119.  
  120.  
  121.     long long ris = dp(N-1);
  122.     printf("%I64d\n", ris);
  123.  
  124.     return 0;
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement