square869120Contest #3 : D - お土産購入計画2 / Souvenirs

これは割とすんなり解けた。
http://s8pc-3.contest.atcoder.jp/tasks/s8pc_3_d

問題

H*Wのグリッドがあり、各セルに数字が振られている。
左上隅のセルから、右または下に隣接するセルをたどり、右下隅のセルに到達するパスを２つ考える。
両パスのいずれかで通過したセルの数字の総和の最大値を求めよ。
(両パスで同じセルを２回通過しても、そのセルは１回分しか総和にカウントされない)

解法

n回隣接セルをたどったのちに存在するセルはmin(H,W)通り以下である。
よって、２つのパスを同時に１マスずつ進めていくことを考えよう。
f(n,a,b) := 2つのパスがそれぞれ左上からn回隣接マスに移動したとき、a列目とb列目に存在する場合の通過した数字の総和の最大値

両パスの次の移動先４通りを順に更新していくDPでf(H+W-2,H-1,H-1)を求めていけばO((H+W)HW)で解ける。

int H,W;
int A[202][202];
ll ma[402][202][202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) cin>>A[y][x];
	ma[0][0][0]=A[0][0];
	
	FOR(i,H+W-2) {
		int y1,y2,x1,x2;
		FOR(y1,H) FOR(y2,H) {
			x1=i-y1;
			x2=i-y2;
			if(x1<0 || x1>=W || x2<0 || x2>=W) continue;
			ll v=ma[i][y1][y2];
			if(x1<W-1 && x2<W-1) { //RR
				if(y1==y2) ma[i+1][y1][y2] = max(ma[i+1][y1][y2],v+A[y1][x1+1]);
				else ma[i+1][y1][y2] = max(ma[i+1][y1][y2],v+A[y1][x1+1]+A[y2][x2+1]);
			}
			if(x1<W-1 && y2<H-1) { // RD
				if(x1+1==x2) ma[i+1][y1][y2+1] = max(ma[i+1][y1][y2+1],v+A[y1][x1+1]);
				else ma[i+1][y1][y2+1] = max(ma[i+1][y1][y2+1],v+A[y1][x1+1]+A[y2+1][x2]);
			}
			if(y1<H-1 && x2<W-1) { // DR
				if(y1+1==y2) ma[i+1][y1+1][y2] = max(ma[i+1][y1+1][y2],v+A[y1+1][x1]);
				else ma[i+1][y1+1][y2] = max(ma[i+1][y1+1][y2],v+A[y1+1][x1]+A[y2][x2+1]);
			}
			if(y1<H-1 && y2<H-1) { //DD
				if(y1==y2) ma[i+1][y1+1][y2+1] = max(ma[i+1][y1+1][y2+1],v+A[y1+1][x1]);
				else ma[i+1][y1+1][y2+1] = max(ma[i+1][y1+1][y2+1],v+A[y1+1][x1]+A[y2+1][x2]);
			}
			
		}
	}
	cout<<ma[H+W-2][H-1][H-1]<<endl;
	
	
}

まとめ

コードは長いけどやってることは単純。