E - Addition and Multiplication 2 ～DP解法～

• Quiz https://atcoder.jp/contests/abc257/tasks/abc257_e
• AC https://atcoder.jp/contests/abc257/submissions/32759201
  • 500ms
  • 計算量O(100N)
• 解説
  • dp[i] : i円使ったときの最大値（値は分布で持つ）
  • iが小さい順に確定していく。配るDP
  • 分布の比較用関数を書く

// Aの方が大ならtrue
// 等しいならfalse
bool my_compare(VI& A, VI& B){
  if(A==B)return false;
  ll sumA = SUM(A);
  ll sumB = SUM(B);
  if(sumA>sumB)return true; // 桁数で上回る
  if(sumA<sumB)return false;
  // 桁数が同じなら
  for(int i=9; i>=1; i--){
    if(A[i]>B[i])return true;
    if(A[i]<B[i])return false;
  }
  return false; // ここに来ることはない
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;cin>>N;

    // dp[i][j]
    // i : i円使った時の最大の値
    // j : 数値jの個数
    VV dp(1000000+5, VI(10));
    
    VI C(10);
    rep(i,9){
      cin>>C[i+1];
    }

    rep(i,N){
      FOR(j,1,10){
        // 番号ｊをえらぶ
        if(i+C[j]>N)continue; // cost over

        ll to = i+C[j];

        // 上書き候補
        VI candidate = dp[i];
        candidate[j]++;

        if(my_compare(candidate, dp[to])){
          dp[to] = candidate;
        }
      }
    }

    VI ma = dp[0];
    rep(i,N){
      if(my_compare(dp[i+1],dp[i])){
        ma = dp[i+1];
      }
    }
    stringstream ss;
    for(int i=9; i>=1; i--){
      rep(j,ma[i]){
        ss << i;
      }
    }
    p(ss.str());

    return 0;
}