CFR 339 C. Xenia and Weights ( DP )
Problem - C - Codeforces
題意:
給 1 ~ 10 重量的法瑪是否存在( 若存在則有無限多個 ),和一個數字 M。輸出一種方案,使得每次輪流放在天平左側右側,且每次放置後由較輕的變為較重的,一共放置 M 個法瑪。求存在否一個合法的序列,若有則輸出。
string seq; int M; void init(){ cin >> seq; cin >> M; } const int INF = 0x3f3f3f3f; const int ZERO = 10; vi C; vvi dp; vvi pre; void preprocess(){ for( int i = 0; i < 10; ++i ) if( seq[ i ] == '1' ) C.push_back( i + 1 ); dp = vvi( M + 1, vi( ZERO * 2 + 1 ) ); dp[ 0 ][ ZERO ] = 1; pre = vvi( M + 1, vi( ZERO * 2 + 1, INF ) ); for( int i = 0; i < M; ++i ){ for( int j = 0; j <= 20; ++j ) if( dp[ i ][ j ] ){ for( int c : C ){ if( abs( pre[ i ][ j ] - j ) == c ) continue; if( j == ZERO ){ if( j + c <= 20 and upmax( dp[ i + 1 ][ j + c ], 1 ) ) pre[ i + 1 ][ j + c ] = j; if( 0 <= j - c and upmax( dp[ i + 1 ][ j - c ], 1 ) ) pre[ i + 1 ][ j - c ] = j; } else if( j < ZERO ){ if( ZERO < j + c and j + c <= 20 and upmax( dp[ i + 1 ][ j + c ], 1 ) ) pre[ i + 1 ][ j + c ] = j; } else{ if( 0 <= j - c and j - c < ZERO and upmax( dp[ i + 1 ][ j - c ], 1 ) ) pre[ i + 1 ][ j - c ] = j; } } } } } void solve(){ for( int i = 0; i <= 20; ++i ) if( dp[ M ][ i ] ){ cout << "YES" << endl; stack< int > ans; for( int m = M, u = i; pre[ m ][ u ] != INF; u = pre[ m ][ u ], --m ) ans.push( abs( u - pre[ m ][ u ] ) ); for( ; not ans.empty(); ans.pop() ) cout << ans.top() << " \n"[ ( int ) ans.size() == 1 ]; return; } cout << "NO" << endl; }