TopCoder SRM 610 Div2 Hard MiningGoldEasy

Hardとはいえ意外とあっさり。
http://community.topcoder.com/stat?c=problem_statement&pm=12931

問題

広大なNxMの２次元領域がある。
この領域では、毎日１か所でD日目まで宝が見つかる。

あなたは、最初任意のマスでスタートし、毎日縦方向または横方向のいずれかに任意の距離移動できる。
移動後、N+M-(宝とあなたの位置のマンハッタン距離)の分だけ利益を得ることができる。
得られる利益を最大化せよ。

解法

単純に宝に近づくのが良い…とは限らない。
ただ、移動する場合は以後登場するどこかの宝にX座標かY座標をそろえるように動くのが良い、ということは想像がつく。
どこの宝のX/Y座標とも一致しない中途半端な位置に止まる意義はない。

よって、移動する可能性があるのはX座標およびY座標がそれぞれD日分でD通りなので、X/Y座標合わせてD^2分のセルだけである。

あとはD^2個のセルに対し、利益を最大化するようDPすればよい。
D日・D^2セル。移動候補縦横D通り、で全部でO(D^4)の時間で済む。

int maxp[51][51][51];

class MiningGoldEasy {
	public:
	int GetMaximumGold(int N, int M, vector <int> event_i, vector <int> event_j) {
		int E=event_i.size();
		int i,x,y,z,ma=0;
		
		ZERO(maxp);
		FOR(x,E) FOR(y,E) {
			maxp[0][x][y]=N+M-abs(event_i[x]-event_i[0])-abs(event_j[y]-event_j[0]);
			ma=max(ma,maxp[0][x][y]);
		}
		FOR(i,E-1) {
			FOR(x,E) FOR(y,E) FOR(z,E) {
				maxp[i+1][z][y]=max(maxp[i+1][z][y], maxp[i][x][y] + N+M-abs(event_i[i+1]-event_i[z])-abs(event_j[i+1]-event_j[y]));
				maxp[i+1][x][z]=max(maxp[i+1][x][z], maxp[i][x][y] + N+M-abs(event_i[i+1]-event_i[x])-abs(event_j[i+1]-event_j[z]));
				ma=max(ma,maxp[i+1][z][y]);
				ma=max(ma,maxp[i+1][x][z]);
			}
		}
		return ma;
		
	}
};

まとめ

いわゆる座標圧縮の１種ともとれるね。