AtCoder ABC #175 : E - Picking Goods

遅刻してなければ…と思うが序盤でWA出しすぎてしょうもない。
https://atcoder.jp/contests/abc175/tasks/abc175_e

問題

H*Wのグリッド上を、左上マスから右または下の隣接マスへの移動を繰り返して右下のマスに移動する。
途中、一部のマスにはお宝があり、その価値が与えられる。
移動経路上にお宝は回収することができるが、同一行では最大3個までしか回収できない。
最適な移動経路と回収戦略を取るとき、得られるお宝の価値の総和の最大値を求めよ。

解法

DPの際に「同一行内での取得済みお宝数」を状態として持ちながらDPしていくだけ。

int H,W,K;
int T[3030][3030];
ll dp[3030][3030][4];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	FOR(i,K) {
		cin>>y>>x>>r;
		T[y-1][x-1]=r;
	}
	
	FOR(y,H) FOR(x,W) {
		for(i=2;i>=0;i--) dp[y][x][i+1]=max(dp[y][x][i+1],dp[y][x][i]+T[y][x]);
		
		FOR(i,4) {
			dp[y+1][x][0]=max(dp[y+1][x][0],dp[y][x][i]);
			dp[y][x+1][i]=max(dp[y][x+1][i],dp[y][x][i]);
		}
	}
	
	
	cout<<dp[H][W-1][0]<<endl;
	
	
}

まとめ

本番は1マスに複数お宝があることを想定したコードを書いてしまった。