# CFR 811 C. Vladik and Memorable Trip ( DP )

Problem - 811C - Codeforces

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;
}
```