ABC104 C (DP) - ゆるふわ競プロ

C問題.苦戦しました.

考察

考察できませんでした。与えられたのが100とか出ていたので全探索するのかと思ったが解説を見て、全探索はダメですと言われて悲しくなった。

今回キーとなる考え方は、100点２問よりも200点２問といたほうがポイントが高いと言う自明なことに気付けるかどうかっと言うことでした。言われてみればそうなんですが実際にといている途中だと頭から抜けていました。完全に全部といた時のボーナスに目がいっていました。

解説見てここまでは理解したが再帰関数をどのように書いていいかがわかりません........(致命傷!!)

とりあえずjavaで書いてある他の方のを見せてもらいましょう。

コードこちらを読みます. 解説では再帰関数と書いてあったがこの解答だとDPを用いている

dp[i] : i個数の問題をといた時にえられる最大点数。

これかけたら今後の応用にも使えそう。頑張って書きましょう。
書いてみた

for (int i = 0; i < d; i++) {
            for (int j = point; j >= 0; j--) {
                for (int k = 0; k < p[i]; k++) {
                    int tmp = dp[j] + (i + 1) * 100 * (k + 1);
                    if (k + 1 == p[i]) {
                        tmp += c[i];
                    }
                    if (tmp > dp[j + k + 1]) {
                        dp[j + k + 1] = tmp;
                    }
                }
            }
            point += p[i];
        }

ほぼ（完全に)丸パクリになってしまった。i,j,kのそれぞれが何を表しているかが重要!

i : i番目まで使っていいと言うこと(3なら300円以下のコインを使えます)
j : j個のコインをみています（i*100円以下の中で)
k : i番目のコインを使う枚数

int tmp = dp[j] + (i + 1) * 100 * (k + 1);この部分では j 個の中の最大値に新しくk+1個数を加えた時の値段を表しています。これと比較して大きければ入れ替えます。

そんなことをやると最終的にDPテーブルが全て埋まります。DPテーブルの中でGより大きい数字の最小の添字を出力すればACできました。