建物 [SoundHound Inc. Programming Contest 2018 (春) D]

https://soundhound2018.contest.atcoder.jp/tasks/soundhound2018_d

前提知識

• 動的計画法（DP）

解法

https://soundhound2018.contest.atcoder.jp/submissions/2036279

以下の説明は、配列や座標などは全て問題文通りの1-indexedで考えていく。
なお、実装では0-indexedでやっている。
「DP[y][x] := 部屋(0,1)から部屋(x,y)へ移動する時の得られる金額の最大値」
これを更新していくことを考えよう。
初期値は「DP[0][1] = 0, DP[0][other] = -INF」
答えはDP[H][1]
DP[y][1～W]と配列P[y+1],F[y+1]からDP[y+1][1～W]を更新していこう。
　
行毎に独立に更新を考えることにする。
「update(dp, P, F) := dp,P,Fを使って次のdpを求めて返す。
この更新の為に配列A,Bを作ろう。
　
A[i] = [1,i)の範囲で得られるお金の最大値
遷移は「i-1 -> i-2 -> ... -> x -> x+1 -> ... -> i-1」
A[1] = 0
A[i] = max(P[i-1]-F[i-1], A[i-1]+P[i-1]-F[i-1]*2)
　
B[i] = (i,W]の範囲で得られるお金の最大値
遷移は「i+1 -> i+2 -> ... -> x -> x-1 -> ... -> i+1」
B[W] = 0
B[i] = max(P[i+1]-F[i+1], B[i+1]+P[i+1]-F[i+1]*2)
　
これを使って、更新していこう。
「ma := [1,i]の範囲でx座標がiまで移動してくるまでの金額の最大値」を更新しながらやっていこう。
ma = max(ma + P[i] - F[i], dp[i] + A[i] + P[i] - F[i]*2, dp[i] + P[i] - F[i])
こうすると、次のdp'はdp'[i] = max(ma + B[i] - F[i], ma)
　
これで大体いいが、これだと遷移が左から右しか出来ないので、左右反転したやつでもやる。
これでDPを更新していく。

int H, W; ll P[10][50101], F[10][50101];
//---------------------------------------------------------------------------------------------------
vector<ll> update(vector<ll> &dp, ll *p, ll *f) {
    vector<ll> A(W), B(W), res(W);
 
    rep(x, 1, W) A[x] = max(p[x - 1] - f[x - 1], A[x - 1] + p[x - 1] - f[x - 1] * 2);
    rrep(x, W - 2, 0) B[x] = max(p[x + 1] - f[x + 1], B[x + 1] + p[x + 1] - f[x + 1] * 2);
 
    ll ma = -infl;
    rep(x, 0, W) {
        ma = max(max(ma + p[x] - f[x], dp[x] + A[x] + p[x] - f[x] * 2), dp[x] + p[x] - f[x]);
        res[x] = max(ma + B[x] - f[x], ma);
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) rep(x, 0, W) cin >> P[y][x];
    rep(y, 0, H) rep(x, 0, W) cin >> F[y][x];
 
    vector<ll> dp(W, -infl);
    dp[0] = 0;
 
    rep(y, 0, H) {
        auto pd1 = update(dp, P[y], F[y]);
 
        reverse(dp.begin(), dp.end());
        reverse(P[y], P[y] + W);
        reverse(F[y], F[y] + W);
 
        auto pd2 = update(dp, P[y], F[y]);
 
        rep(x, 0, W) dp[x] = max(pd1[x], pd2[W - 1 - x]);
    }
 
    rep(x, 0, W) printf("%lld\n", dp[x]);
}