Codeforces 213C Relay Race

問題

nxnのそれぞれのマスに数字a[i][j]が書かれたグリッドがある。
Aさんがグリッドの左上から右下まで、右か下だけに移動しながら移動する
Bさんがグリッドの右下から左上まで、左か上だけに移動しながら移動する

このとき、「二人の少なくともどちらかが通ったマス」の数字の和をできるだけ大きくしたい。
その最大値を求めよ。

制約条件

n≦300
-1000≦a[i][j]≦1000

方針

DP.
まず、二人が左上から右下に移動すると考えても同じなのでそう考える。
また、AさんはBさんの常に同じか上側にいると考えても最大値は変わらない。

dp[i][j][k]を、Aさんが(j, i)、Bさんが(k, i)にいるときの和の最大値とする。
これを更新するようなDPをしたい。

が、上にいるAさんが下向きに移動したとき、
そのマスをすでにBさんが通っているか通ってないかで和に足されるか足されないかが変わる。

なので、一列にAさん（上）Bさん（下）がいるとき、
最初にBさんだけが動いて、一旦Bさんが動いたら、Aさんは動けないようにすることでその問題を解消できる。

ソースコード

int n, a[300][300], dp[300][300][300][2];

int main(){
	cin >> n;
	rep(i, n) rep(j, n){
		cin >> a[i][j];
		rep(k, n) rep(l, 2) dp[i][j][k][l] = -inf;
	}
	dp[0][0][0][1] = a[0][0];
	rep(i, n) rep(j, n) rep(k, n){
//まだBさんが動いていない
		if(dp[i][j][k][0] > -inf){
			if(j+1 < k) dp[i][j+1][k][0] = max(dp[i][j+1][k][0], dp[i][j][k][0] + a[j+1][i]);
//次で二人が重なるときは和に入らない
			if(j+1 ==k) dp[i][j+1][k][1] = max(dp[i][j+1][k][1], dp[i][j][k][0]);
			
			if(k+1 < n) dp[i][j][k+1][1] = max(dp[i][j][k+1][1], dp[i][j][k][0] + a[k+1][i]);
			if(i+1 < n) dp[i+1][j][k][0] = max(dp[i+1][j][k][0], dp[i][j][k][0] + a[j][i+1] + a[k][i+1]);
		}
		if(dp[i][j][k][1] > -inf){
//重なっているときは、一人分しか足されない
			if(j==k && j+1 < n) dp[i][j+1][k+1][1] = max(dp[i][j+1][k+1][1], dp[i][j][k][1] + a[j+1][i]);
			if(k+1 < n) dp[i][j][k+1][1] = max(dp[i][j][k+1][1], dp[i][j][k][1] + a[k+1][i]);
			
			if(i+1 < n && j != k) dp[i+1][j][k][0] = max(dp[i+1][j][k][0], dp[i][j][k][1] + a[j][i+1] + a[k][i+1]);
			if(i+1 < n && j == k) dp[i+1][j][k][1] = max(dp[i+1][j][k][1], dp[i][j][k][1] + a[j][i+1]);
		}
	}
	//dbg(dp[0][0][1][1]);
	cout << dp[n-1][n-1][n-1][1] << endl;
	return 0;
}