0w1

CFR 509 C. Sums of Digits ( DP )

Problem - C - Codeforces

題意:
給 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;
  }
}