■

All Green をDPで解いた

All Green をDPでACしたので、その解説をしたいと思います

DP初心者なので無駄が多いかもしれませんがごめんなさい><

問題概要

 それぞれの問題には、難易度に応じて点数が付けられています。 現在、$1$ 以上 $D$ 以下のそれぞれの整数 $i$ に対して、$100i$ 点を付けられた問題が $p_i$ 問存在します。 これらの $p_1+\dots +p_D$ 問が 問題のすべて。

 ユーザーの総合スコアは、以下の $2$ つの要素の和です。

• 基本スコア: ユーザーが解いた問題すべての配点の合計です。
• コンプリートボーナス: $100i$ 点を付けられた $p_i$ 問の問題すべてを解いたユーザーは、基本スコアと別にコンプリートボーナス $c_i$ 点を獲得します $(1\le i\le D)$。

 彼の目標は、総合スコアを $G$ 点以上にすることです。 このためには、少なくとも何問の問題を解く必要があるでしょうか？

解説

まずはDPテーブル(あってる？)を考えます

僕はdp[i][j](i番目まで見て、合計j個の問題をすでに解いている際における総合スコアの最大値)と定義しました

次に遷移を考えましょう

この問題における状態とは、ある問題を解くか否かの高々2通りです

これをそのままDPの遷移としてあらわしてやればよいです

具体的にDP漸化式を定義すると、(ここでkとはi番目の問題をk個解くという状態を示し、bonusはkがa[i]の時b[i],そのほかでは0として扱うと定義します)

dp[i+1][j+k]=max(dp[i+1][j+k],dp[i][j]+100*(i+1)*k+bonus)

以上の遷移を行い、dp[n][j]>=Gを満たす最小のjを出力すればACを獲得することができます

D<=10 p[i]<=100 であることから十分に間に合います