[AtCoder] ABC 175 E – Picking Goods

問題

方針

マス \( (i, j)\) にあるアイテムの価値を \( g(i, j) \) とします。アイテムがない場合は \( 0 \) とします。次に、マス \( (i, j)\) において \( i \) 行目のアイテムを \( k \) 個取った時のアイテムの価値の合計の最大値を \( a(i, j, k) \) とします。この配列を動的計画法によって更新します。

マス \( (i, j)\) から マス \( (i + 1, j) \) に移動するとき

このとき、マス \( (i + 1, j) \) のアイテムを拾うか拾わないかの選択があるので、アイテムを拾わないとき、

\[ a(i + 1, j, 0) = \max(a(i + 1, j, 0), \ a(i, j, k)) \ (0 \leq k \leq 3)\]

となり、アイテムを拾うとき、

\[ a(i + 1, j, 1) = \max(a(i + 1, j, 1), \ a(i, j, k) + g(i + 1, j)) \ (0 \leq k \leq 3)\]

と更新されます。

マス \( (i, j)\) から マス \( (i , j + 1) \) に移動するとき

上記と同様に、マス \( (i + 1, j) \) のアイテムを拾わないとき、

\[ a(i, j + 1, k) = \max(a(i, j + 1, 0), \ a(i, j, k)) \ (0 \leq k \leq 3)\]

アイテムを拾うとき、アイテムを \( 3 \) 個持っている状態からは遷移できないことに注意して、

\[ a(i, j + 1, k + 1) = \max(a(i, j + 1, 0), \ a(i, j, k) + g(i, j + 1)) \ (0 \leq k \leq 2)\]

となります。

コード