0w1

IOI 2016 Paint ( DP )

http://ioinformatics.org/locations/ioi16/contest/day2/paint/paint-TWN.pdf
1959 - [IOI 2016] Paint | TIOJ INFOR Online Judge

題意:
給一個序列含 '.', 'X', '_',分別代表該位置的字符為未知、必為黑色、必為白色。再給 K 個數字 C[],代表由左到右看這個序列,有 K 個黑色連續區間,第 i 個的長度為 C[ i ]。不同的黑色連續區間不可以重疊,也不可以接觸。求對於每一個位置,是一定是黑色,或一定是白色,或不一定。

資料規模:
N ≤ 2e5
K ≤ 100

解法:
dpf[ i ][ j ][ k ] : 已考慮前 i 個字符,已完成 j 個要求,最後一個完成的要求是黑色的 = 1
dpb[ i ][ j ][ k ] : 反轉 s 和 c 陣列後做的 dpf
因為有從前面做的跟從後面做的,所以可以驗證一個點是否可以是白色或黑色的
至於黑色是否可行,因為也許在連續區間的中間,所以從左邊掃過去,每次更新右界最大值去看是否涵蓋在裡面。
據說只用一個 dp 也可以做 ( ?

時間 / 空間複雜度:
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;
}*/