All Green [AtCoder Beginner Contest 104 C]

https://beta.atcoder.jp/contests/abc104/tasks/abc104_c

前提知識

• 動的計画法

解法

https://beta.atcoder.jp/contests/abc104/submissions/2956491

点数は全て100の倍数なので、全て100分の1にして考えることにする。
Gの上限が書かれていないので、上限をまずは見積もろう。
取りうる最大得点は
問題で得られる得点：1*100+2*100+3*100+...+10*100=5500
ボーナスで得られる得点：10^4*10=10^5
なので10^5+5500が最大得点になる。よって、これがGの上限。
　
ここからDPを考える。
dp[i][point] := i番目の問題まででpoint点得るための最小問題数
遷移はi+1番目で何個取るかなので、最大100通り。
iは10通りでpointは10^5位なので、全体で10^8くらいになる。
DPは基本軽いのでこれくらいなら大丈夫。
あとは、pointがG以上で問題数が小さいものを取ると答え。

※書いてて気がついたが「dp[i][num] := i番目の問題まででnum問題解いたときの最大点数」でやったほうが良かったかも

int D, G, P[10], C[10];
int dp[11][401010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> D >> G;
    rep(i, 0, D) cin >> P[i] >> C[i];
 
    G /= 100;
    rep(i, 0, D) C[i] /= 100;
 
    rep(i, 0, D + 1) rep(point, 0, 201010) dp[i][point] = inf;
    dp[0][0] = 0;
 
    rep(i, 0, D) rep(point, 0, 201010) {
        rep(j, 0, P[i]) chmin(dp[i + 1][point + (i + 1)*j], dp[i][point] + j);
        chmin(dp[i + 1][point + (i + 1)*P[i] + C[i]], dp[i][point] + P[i]);
    }
 
    int ans = inf;
    rep(point, G, 201010) chmin(ans, dp[D][point]);
    cout << ans << endl;
}