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

問題概略
H*Wのグリッドがあり、そこにはお金Pと入場料Fがある。
上以外へ移動できる時、[H][1~W]での最大かねを求めよ
H <=10 W <= 5*10^5
p,f <10^5

解法
解説見てもよくわからなかったので、kmjpさんの実装をみて理解しました
Submission #2022964 - SoundHound Inc. Programming Contest 2018 (春)

editorialより、sの右側にTがあるとき、
１　sから左側へいくつか進んでsへ戻り、
２　sからtまで進み
3 tから右側へいくつか進んでtへ戻る
の3つが必要だとわかる。

dp[h][w] := [h][w]での最大値として、
制約的にdp[h][w]の値をO(1)で求める必要がある。
また、形的に貰うDPでないといけない

L[w] := wについたあとに、いくつか左へ進み、wに戻ってくる時の最大増加量
L2[w] := wより左側の点zまで左へ進み、wまで進んだ時の最大増加量とする

ここで、L2[w]の点zはL2[w-1]の時の物か、wであることがわかり、漸化的に遷移できる

#define int long long
ll u(ll a) {
return a < 0 ? 0 : a;
}

int N, H, W, A[101010];
int G[11][101010], F[11][101010];
int L[11][101010], R[11][101010];
int L2[11][101010], R2[11][101010];
int C[11][101010];

signed main() {
cin >> H >> W;
nt(G, H, W);
nt(F, H, W);
fill(C, -LINF);
for (int i = 0; i < W; ++i) {
C[0][i] = G[0][i] - F[0][i];
if (i)C[0][i] += C[0][i - 1];
}
rer(i, W - 2) {
R[0][i] = u(R[0][i + 1] + G[0][i + 1] - F[0][i + 1] - F[0][i]);
C[0][i] += R[0][i];
}
for (int h = 1; h < H; ++h) {
rep(i, 1, W) L[h][i] = u(L[h][i - 1] + G[h][i - 1] - F[h][i - 1] - F[h][i]);
rer(i, W - 2) R[h][i] = u(R[h][i + 1] + G[h][i + 1] - F[h][i + 1] - F[h][i]);
rer(i, W - 1) {
R2[h][i] = C[h - 1][i] + G[h][i] - F[h][i] + R[h][i];
if (i < W - 1)chmax(R2[h][i], R2[h][i + 1] + G[h][i] - F[h][i]);
chmax(C[h][i], R2[h][i] + L[h][i]);
}
rep(i, W) {
L2[h][i] = C[h - 1][i] + G[h][i] - F[h][i] + L[h][i];
if (i)chmax(L2[h][i], L2[h][i - 1] + G[h][i] - F[h][i]);
chmax(C[h][i], L2[h][i] + R[h][i]);
}
}
for (int i = 0; i < W; ++i) {
cout << C[H - 1][i] << endl;
}

return 0;
}