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