はまやんはまやんはまやん

hamayanhamayan's blog

森林伐採 (Deforestation) [JOI/IOI 第17回日本情報オリンピック 予選 E]

https://atcoder.jp/contests/joi2018yo/tasks/joi2018_yo_e

解法

https://atcoder.jp/contests/joi2018yo/submissions/8137468

最初考えた微妙な解法。
まず、通る必要のない部分は木を伐採する必要は無いので、北西から南東まで1つのパスを掘ればいいことになる。
この手の問題はまずダイクストラかな?という感じがあるので、そっち方面で考えてみる。
状態は座標(x,y)と取れば良さそうだが、北西端までの経路によってコストが変化するので、これだけでは足りない。
状態を「(x,y,d) := 座標(x,y)で北西端までの距離がd」としてダイクストラしよう。
状態数はO(H^2W^2)くらいなので大丈夫。
遷移数も上下左右の4なので大丈夫。
 
公式の答えはDP解法であった。
確かに今回はこのように状態を作るとサイクルが無いため、こっちの方がいい。
dp[x][y][d] := 座標(x,y)で北西端までの距離がdの状態にするまでに必要な最小時間
遷移はdp[x][y][d]からdp[x+1][y][d+1],dp[x-1][y][d+1],dp[x][y+1][d+1],dp[x][y-1][d+1]へである。
座標を埋める順番に注意する必要があるが、dが小さい順に埋めていこう。

int H, W, A[40][40];
int dp[40][40][1010];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) rep(x, 0, W) cin >> A[y][x];

    rep(y, 0, H) rep(x, 0, W) rep(d, 0, H * W) dp[x][y][d] = inf;
    dp[0][0][0] = 0;

    rep(d, 0, H * W) rep(x, 0, W) rep(y, 0, H) {
        rep(di, 0, 4) {
            int xx = x + dx[di];
            int yy = y + dy[di];
            if (0 <= xx and xx < W and 0 <= yy and yy < H) {
                int c = dp[x][y][d] + A[yy][xx] * (1 + 2 * d);
                chmin(dp[xx][yy][d + 1], c);
            }
        }
    }

    int ans = inf;
    rep(d, 0, H * W) chmin(ans, dp[W - 1][H - 1][d]);
    cout << ans << endl;
}