[AtCoder ABC104 C All Green ] DP

(問題ページ) AtCoder ABC104 C All Green
https://atcoder.jp/contests/abc104/tasks/abc104_c

---

DPで解いた例です

1.考え方

dp[i][j]: (i+1)番目の問題を解いたときに、合計でj問解いていたときの、最大得点。

(i+1)番目の問題を解くときに、問題数を0～p[i]まで変化させて、DPテーブルの更新をします。(変数kを使用)
そのため、for文で変数i,j,kを用いた3重ループになります。

dpテーブルには、初期値-1を入れておき、「-1だった時、breakさせる」ことで、上記3重ループにpruning的なことをしています。

2.code

#include <iostream>
#include <vector>
using namespace std;


int main() {
    int D, G;
    cin >> D >> G;

    int p[D], c[D];
    for (int i = 0; i < D; i++) {
        cin >> p[i] >> c[i];
    }

    vector<vector<int>> dp(D+1, vector<int>(1101, -1));
    dp[0][0] = 0;

    for (int i = 0; i < D; i++) { // i: index
        for (int j = 0; j < 1001; j++) {  // j: the total number of the problems solved
            if (dp[i][j] == -1) {
                break;
            }
            for (int k = 0; k < p[i]; k++) {  // k: the number of the problem-p[i] solved
                dp[i+1][j+k] = max(dp[i+1][j+k], dp[i][j] + (i+1)*100*k);
            }
            int k = p[i];
            dp[i+1][j+k] = max(dp[i+1][j+k], dp[i][j] + (i+1)*100*k + c[i]);
        }
    }

    int ans = 1001;
    for (int i = 1; i < (D+1); i++) {
        for (int j = 1; j < 1001; j++) {
            if (dp[i][j] >= G) {
                ans = min(ans, j);
                break;
            }
        }
    }
    printf("%d\n", ans);
}