# IOI 2016 Paint ( DP )

N ≤ 2e5
K ≤ 100

dpf[ i ][ j ][ k ] : 已考慮前 i 個字符，已完成 j 個要求，最後一個完成的要求是黑色的 = 1
dpb[ i ][ j ][ k ] : 反轉 s 和 c 陣列後做的 dpf

O( N * K )

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

const int MAXN = ( int ) 2e5;
const int MAXK = 100;

int pfx[ MAXN + 1 ];
bool dpf[ MAXN + 1 ][ MAXK + 1 ][ 2 ];
bool dpb[ MAXN + 1 ][ MAXK + 1 ][ 2 ];

void solve_puzzle( int n, char* s, int k, int* c, char* result ){
memset( dpf, 0, sizeof( dpf ) );
memset( dpb, 0, sizeof( dpb ) );
for( int i = 0; i < n; ++i ){
pfx[ i + 1 ] = pfx[ i ] + ( s[ i ] == '_' );
}
dpf[ 0 ][ 0 ][ 0 ] = 1;
for( int i = 0; i < n; ++i ){
for( int j = 0; j <= k; ++j ){
if( s[ i ] != 'X' ){
dpf[ i + 1 ][ j ][ 0 ] |= dpf[ i ][ j ][ 0 ] or dpf[ i ][ j ][ 1 ];
}
if( j + 1 <= k and i + c[ j ] <= n and pfx[ i + c[ j ] ] - pfx[ i ] == 0 ){
dpf[ i + c[ j ] ][ j + 1 ][ 1 ] |= dpf[ i ][ j ][ 0 ];
}
}
}
reverse( s, s + n );
for( int i = 0; i < n; ++i ){
pfx[ i + 1 ] = pfx[ i ] + ( s[ i ] == '_' );
}
dpb[ 0 ][ 0 ][ 0 ] = 1;
for( int i = 0; i < n; ++i ){
for( int j = 0; j <= k; ++j ){
if( s[ i ] != 'X' ){
dpb[ i + 1 ][ j ][ 0 ] |= dpb[ i ][ j ][ 0 ] or dpb[ i ][ j ][ 1 ];
}
if( j + 1 <= k and i + c[ k - 1 - j ] <= n and pfx[ i + c[ k - 1 - j ] ] - pfx[ i ] == 0 ){
dpb[ i + c[ k - 1 - j ] ][ j + 1 ][ 1 ] |= dpb[ i ][ j ][ 0 ];
}
}
}
int furthest = 0;
for( int i = 1; i <= n; ++i ){
int white = 0, black = 0;
for( int j = 0; j <= k; ++j ){
white |= dpf[ i ][ j ][ 0 ] and dpb[ n - ( i - 1 ) ][ k - j ][ 0 ];
if( j + 1 <= k and dpf[ i - 1 ][ j ][ 0 ] and dpb[ n - ( i - 1 ) ][ k - j ][ 1 ] ){
furthest = max( furthest, i + c[ j ] ); // [ i, furthest ) : 1 base
}
}
black |= i < furthest;
if( white and not black ) result[ i - 1 ] = '_';
else if( black and not white ) result[ i - 1 ] = 'X';
else result[ i - 1 ] = '?';
}
}

/*signed main(){
int n; char s[ 1000 ]; int k; int c[ 1000 ]; char result[ 1000 ];
scanf( "%d\n%s\n%d\n", &n, s, &k );
for( int i = 0; i < k; ++i ){
scanf( "%d", &c[ i ] );
}
solve_puzzle( n, s, k, c, result );
for( int i = 0; i < n; ++i ){
printf( "%c", result[ i ] );
}
puts( "" );
return 0;
}*/
```