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;
}