[AtCoder] ABC 015 D – 高橋くんの苦悩

問題

方針

ナップサック問題なので動的計画法で解きます。\( d(i, j, k) \) を スクリーンショット \( i \) まで見た時、\( j \) 枚貼り付けて幅が \( k \) であるときの重要度の合計の最大値とします。遷移式は、

\[ d(i + 1, j , k) = d(i, j, k)\]

と初期化したあとに、

\[ d(i + 1, j + 1, k + A_i) \leftarrow \max(d(i + 1, j + 1, k + A_i), d(i, j, k) + B_i)\]

となります。

コード