PAST to Fishing [第六回 アルゴリズム実技検定 I]

https://atcoder.jp/contests/past202104-open/tasks/past202104_i

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/past202104-open/submissions/22654667

DPに慣れていると問題設定と制約を見るとDPかなと一直線で結びついてしまう。
考察過程が何もないのだが、多分以下のようなことを考えているのだろうと思う。

• 1～H+W-1までの全てのkについて答える必要がある
• 最大値を求める問題である
• 移動が一方通行であり、セルを頂点、移動を辺として見ると、DAGとなる

動的計画法

次元数がやや高いDPテーブルを構築する。
座標はすべて0-indexedで書いている。

dp[y][x][fish] := 現在セル(x,y)にいてここまでの釣りが完了しているときに、釣った魚の合計がfish匹である場合の美味しさの総和の最大値

最初は(0,0)から始まるが、そこまでの釣りは完了していることを過程しているので、

dp[0][0][0] = 0
dp[0][0][1] = A[0][0]

が初期状況となる。
遷移は↓と→のどちらに移動するかの2択と、移動先で釣りをするかしないかの2択があるので、4択の遷移がある

dp[y + 1][x][fish] ← dp[y][x][fish]
dp[y + 1][x][fish + 1] ← dp[y][x][fish] + A[y + 1][x]
dp[y][x + 1][fish] ← dp[y][x][fish]
dp[y][x + 1][fish + 1] ← dp[y][x][fish] + A[y][x + 1]

これでdp[H-1][W-1][fish]を使えば答えられる。

int H, W, A[101][101];
ll dp[101][101][201];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) rep(x, 0, W) cin >> A[y][x];

    dp[0][0][0] = 0;
    dp[0][0][1] = A[0][0];

    rep(y, 0, H) rep(x, 0, W) rep(fish, 0, H + W) {
        if (y + 1 < H) {
            chmax(dp[y + 1][x][fish], dp[y][x][fish]);
            chmax(dp[y + 1][x][fish + 1], dp[y][x][fish] + A[y + 1][x]);
        }
        if (x + 1 < W) {
            chmax(dp[y][x + 1][fish], dp[y][x][fish]);
            chmax(dp[y][x + 1][fish + 1], dp[y][x][fish] + A[y][x + 1]);
        }
    }

    rep(fish, 1, H + W) printf("%lld\n", dp[H - 1][W - 1][fish]);
}