【ABC210】D - National Railway

atcoder.jp

解法

絶対値を外すことができれば、(i, j)と(i', j') を分離できるので計算しやすくなる。
そこで、i ≧ i'かつ j ≧ j' という条件をつけることにする。
これで絶対値の中が必ず0以上になるため、絶対値を外して計算できるようになる。
i < i' かつ j < j' の時はどうすればよいか、というとこれはグリッドを左右反転させることでなんとかできる。
(それ以外のパターンは (i, j) と (i', j')を入れ替えれば成り立つため、一般性は失わない)

ここで、次のようなDPを考える。
dp[i][j] ← 既に何処かに駅を建てて、(i, j)まで来たときの費用の最小値
ただし、駅を建てた場所を(i', j') とすると、i ≦ i'かつ j ≦ j' という条件をつけることにする。
(上の絶対値を外す条件と(i, j)と(i', j')を逆にしただけです。分かりにくくてごめんなさい。)
条件をつけているのは、絶対値を外して計算するため。

このDPは次のように遷移する。
dp[i][j] ← min(A[i][j], dp[i-1][j] + C, dp[i][j-1] + C)
左から順に、(i, j)に駅を立てる場合、既に何処かに駅を建てて(i-1, j)からやってきた場合、(i, j-1)からやってきた場合を表す。

あとはこのDPの結果を利用して答えを出す。
(i', j')を全探索して、 min(dp[i'-1][j'] + C + A[i'][j'], dp[i'][j'-1] + C + A[i'][j']) の最小値が答えになる。

実装

i < i' かつ j < j' の時を考える必要があるため、グリットを左右反転させたものでも計算する。

void solve(long long H, long long W, long long C, std::vector<std::vector<long long>> A) {
    vector<vector<long long>> dp1(H, vector<long long>(W, INF64)),
    dp2(H, vector<ll>(W, INF64));

    vector<vector<int>> direction1 = {{0, -1}, {-1, 0}};
    vector<vector<int>> direction2 = {{0, 1}, {-1, 0}};

    ll ans = INF64;
    REP (i, H) {
        REP (j, W) {
            dp1[i][j] = A[i][j];
            dp2[i][W-j-1] = A[i][W-j-1];

            REP (k, 2) {
                int py = i + direction1[k][0];
                int px = j + direction1[k][1];

                if (py < 0 || px < 0) continue;

                chmin(dp1[i][j], dp1[py][px] + C);

                chmin(ans, dp1[py][px] + C + A[i][j]);
            }

            REP (k, 2) {
                int py = i + direction2[k][0];
                int px = (W-j-1) + direction2[k][1];

                if (py < 0 || px >= W) continue;

                chmin(dp2[i][W-j-1], dp2[py][px] + C);

                chmin(ans, dp2[py][px] + C + A[i][W-j-1]);
            }
        }
    }

    c(ans) 
}

学んだこと

• 絶対値を外すために条件をつけると良いことがある
• 直接答えを求める以外にDPを使うことがある

↓解説が分かりやすかった。 atcoder.jp

blog.hamayanhamayan.com