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; }*/