CFR 811 C. Vladik and Memorable Trip ( DP )

Problem - 811C - Codeforces

題意：
給長度 N 的數列 A[]。你想要取出若干個連續數列，使得每個數列中相異元素的 XOR 和，之和最大。
但是有個條件，如果某個元素 x 在取出的某個數列裡，那麼所有元素 x 都必須在該數列中。

制約：
1 ≤ N ≤ 5000
0 ≤ A[ i ] ≤ 5000

解法：
dp[ i ]：[ 0, i ) 的子問題的答案，但是對於 [ i, N ) 中的元素有滿足題目的特殊條件。
更新時，若且唯若這個打算新納入的數列的開頭的元素是第一次出現的，才能進行更新。
而且，一旦找到不能取的 ( 這個元素已經出現過，而且在這個開頭的左邊 )，就立刻結束。
否則，要至少往右繼續走到當前這個數列中最後一次出現的都被包含在這個數列裡，才可以更新。

複雜度：
O( N ** 2 )

#include <bits/stdc++.h>
using namespace std;

template< class T1, class T2 >
int upmax( T1 &x, T2 v ) {
  if( x >= v ) return 0;
  x = v;
  return 1;
}

const int MAXN = 5000;
const int MAXA = 5000;

int N;
int A[ MAXN ];
int pA[ MAXN + 1 ];
int first[ MAXA + 1 ];
int last[ MAXA + 1 ];

int dp[ MAXN + 1 ];

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N;
  memset( first, -1, sizeof( first ) );
  for( int i = 0; i < N; ++i ) {
    cin >> A[ i ];
    pA[ i + 1 ] = pA[ i ] ^ A[ i ];
    if( first[ A[ i ] ] == -1 ) {
      first[ A[ i ] ] = i;
    }
    last[ A[ i ] ] = i;
  }
  for( int i = 0; i < N; ++i ) {
    upmax( dp[ i + 1 ], dp[ i ] );
    if( first[ A[ i ] ] != i ) continue;
    static int vis[ MAXA + 1 ];
    int ptr = i;
    int score = 0;
    int mxb = i;
    while( ptr < N ) {
      if( vis[ A[ ptr ] ] != i + 1 and first[ A[ ptr ] ] != ptr ) break; // torenai
      vis[ A[ ptr ] ] = i + 1;
      if( ptr == first[ A[ ptr ] ] ) {
        score ^= A[ ptr ];
      }
      upmax( mxb, last[ A[ ptr ] ] );
      if( ptr == mxb ) {
        upmax( dp[ mxb + 1 ], dp[ i ] + score );
      }
      ++ptr;
    }
  }
  cout << dp[ N ] << endl;
  return 0;
}