解法

概要

としても本質は同じ。 とりあえずのDPを書いて適当にすると、線形性により変数関数の最大値を変数化し差分更新できてになる。 全体で$O(HW)$。

詳細

次のようにおく:

  • : 部屋に既にいる時点から始めて、好きなだけ左へ行ってから戻ってくるときの獲得金額の最大値
  • : 部屋に既にいる時点から始めて、部屋までまっすぐ移動するときの獲得金額。ただし
  • : 部屋に既にいる時点から始めて、好きなだけ右へ行ってから戻ってくるときの獲得金額の最大値

このときDPで求める関数は

であるが、これは

と書き直せる。 内側の最大化対象の関数がのみの関数になったため、異なる同士でその計算結果を使い回せてに落ちる。

メモ

実装

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
using ll = long long;
using namespace std;
template <class T, class U> inline void chmax(T & a, U const & b) { a = max<T>(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

constexpr ll INF = (ll)1e18 + 9;
vector<ll> solve(int h, int w, vector<vector<ll> > const & ps, vector<vector<ll> > const & fs) {
    vector<ll> cur(w, - INF), prv;
    cur[0] = 0;

    REP (y, h) {
        auto const & p = ps[y];
        auto const & f = fs[y];
        vector<ll> m(w + 1);
        REP (x, w) {
            m[x + 1] = m[x] + p[x] - f[x];
        }
        vector<ll> l(w);
        REP (x, w - 1) {
            l[x + 1] = max(0ll, l[x] + p[x] - f[x] - f[x + 1]);
        }
        vector<ll> r(w);
        REP_R (x, w - 1) {
            r[x] = max(0ll, r[x + 1] + p[x + 1] - f[x + 1] - f[x]);
        }

        cur.swap(prv);
        cur.assign(w, - INF);

/*
        // O(W^2)
        REP (x, w) {
            REP (x1, w) {
                if (x1 < x) {
                    chmax(cur[x], prv[x1] + l[x1] + m[x + 1] - m[x1] + r[x]);
                } else {
                    chmax(cur[x], prv[x1] + l[x] + m[x1 + 1] - m[x] + r[x1]);
                }
            }
        }
*/

        // O(W)
        ll acc = - INF;
        REP (x, w) {
            chmax(cur[x], acc + m[x + 1] + r[x]);
            chmax(acc, prv[x] + l[x] - m[x]);
        }
        acc = - INF;
        REP_R (x, w) {
            chmax(acc, prv[x] + r[x] + m[x + 1]);
            chmax(cur[x], acc + l[x] - m[x]);
        }
    }
    return cur;
}

int main() {
    int h, w; cin >> h >> w;
    auto p = vectors(h, w, 0ll);
    auto f = vectors(h, w, 0ll);
    REP (y, h) REP (x, w) cin >> p[y][x];
    REP (y, h) REP (x, w) cin >> f[y][x];
    auto answer = solve(h, w, p, f);
    for (auto it : answer) cout << it << endl;
    return 0;
}