Codeforces 429(#245 Div1) B. Working out
問題
hxwのグリッドがある。各セルには得点が定められている。
Aは(1, 1)から(h, w)へ移動し、Bは(h, 1)から(1, w)へ移動する。
Aは右または下にのみ移動できて、Bは右または上にのみ移動できる。
A, Bの軌跡で共通部分はただ1つのセルでなければならない。
共通部分のセルではA, Bは二人とも得点を得ることはできず、他のセルでは書かれている得点が得られる。
このとき、A, B得られる得点の和の最大値を求めよ。
制約条件
h, w≦1000
方針
動的計画法。
二人ともが通るマスは1つしかないので、
Aが上から入って下に抜けて、Bが左から入って右に抜けるか、
Aが左から入って右に抜けて、Bが下から入って上に抜けるしかない。
それぞれの場合で、入るまでと出た後の得点の最大値を予めDPで求めておいて、
全てのマスについて最大値を求めればいい。
出た後と出る前のDPは、4方向なので4回DPしておく必要がある。
ソースコード
int h, w, a[1000][1000]; int dp[4][1000][1000]; int main(){ cin >> h >> w; rep(i, h) rep(j, w) cin >> a[i][j]; rep(it, 4){ if(it & 1) rep(i, h / 2) rep(j, w) swap(a[h - 1 - i][j], a[i][j]); if(it & 2) rep(i, h) rep(j, w / 2) swap(a[i][w - 1 - j], a[i][j]); dp[it][h - 1][w - 1] = a[h - 1][w - 1]; for(int i = h - 1; i >= 0; i--) for(int j = w - 1; j >= 0; j--){ if(i) dp[it][i - 1][j] = max(dp[it][i - 1][j], dp[it][i][j] + a[i - 1][j]); if(j) dp[it][i][j - 1] = max(dp[it][i][j - 1], dp[it][i][j] + a[i][j - 1]); } if(it & 1) rep(i, h / 2) rep(j, w) swap(a[h - 1 - i][j], a[i][j]); if(it & 2) rep(i, h) rep(j, w / 2) swap(a[i][w - 1 - j], a[i][j]); if(it & 1) rep(i, h / 2) rep(j, w) swap(dp[it][h - 1 - i][j], dp[it][i][j]); if(it & 2) rep(i, h) rep(j, w / 2) swap(dp[it][i][w - 1 - j], dp[it][i][j]); } int ans = -1; for(int i = 1; i < h - 1; i++) for(int j = 1; j < w - 1; j++) rep(d, 2){ ans = max(ans, dp[3][i - d][j - !d] + dp[0][i + d][j + !d] + dp[1][i - !d][j + d] + dp[2][i + !d][j - d]); } cout << ans << endl; return 0; }