CFR 509 C. Sums of Digits ( DP )
題意:
給 N 個數字, B[ i ] 代表第 i 個數字各位數總和為 B[ i ]。求可能對應的數列的最後一個值的最小可能,且須滿足數列嚴格遞增。
資料規模:
The first line contains a single integer number n (1 ≤ n ≤ 300).
Next n lines contain integer numbers b1, ..., bn — the required sums of digits. All bi belong to the range 1 ≤ bi ≤ 300.
TL: 2000 ms
ML: 256 MB
解法:
非常難寫的一題。 首先顯然每一步都要做最小值。第 i 步事實上要做的是對第 i - 1 個值,增加 B[ i ] - B[ i - 1 ] 為數,且變大。如果這個值是正的,那麼考慮從最小位開始加,每次加滿 ( 加到 9 )。如果非正,那麼就從最小的值開始拿光 ( 拿到剩 0 ),直到有 1,就把那個 1 往更高的最低位增加,並把增加的位以下的數收集起來,再從最小為開始加滿。
時間 / 空間複雜度:
O( N * B )
int N; vi B; void init(){ cin >> N; B = vi( N ); for( int i = 0; i < N; ++i ){ cin >> B[ i ]; } } void add( vi &vec, int m ){ for( int i = 0; i < vec.size(); ++i ){ if( m + vec[ i ] <= 9 ){ vec[ i ] += m; return; } m -= 9 - vec[ i ]; vec[ i ] = 9; } while( m ){ vec.emplace_back( min( 9, m ) ); m -= min( 9, m ); } } vvi ans; void preprocess(){ ans = vvi( N ); add( ans[ 0 ], B[ 0 ] ); for( int i = 1; i < N; ++i ){ ans[ i ] = ans[ i - 1 ]; int m = B[ i ] - B[ i - 1 ]; if( m <= 0 ){ for( int j = 0; j < ans[ i ].size(); ++j ){ if( m + ans[ i ][ j ] > 0 ){ --ans[ i ][ j ]; int z = 1; for( int k = j + 1; k < ans[ i ].size(); ++k ){ if( ans[ i ][ k ] + 1 < 10 ){ ++ans[ i ][ k ]; z = 0; for( int l = k - 1; l >= 0; --l ){ m += ans[ i ][ l ]; ans[ i ][ l ] = 0; } break; } } if( z ){ for( int k = 0; k < ans[ i ].size(); ++k ){ m += ans[ i ][ k ]; ans[ i ][ k ] = 0; } ans[ i ].emplace_back( z ); } break; } m += ans[ i ][ j ]; ans[ i ][ j ] = 0; } } add( ans[ i ], m ); } } void solve(){ for( int i = 0; i < N; ++i ){ for( int j = ans[ i ].size() - 1; j >= 0; --j ){ cout << ans[ i ][ j ]; } cout << endl; } }