AOJ 0581 Gifts

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0581）

h, wのグリッドの左上から右下まで、右または下に移動することを繰り返して到達する。
#のマスには進入できず、数字のマスに進入すると、
最初の一回だけその数字の分だけ得点が得られる。

k回だけ、上または左に戻ることができるとき、
得られる得点の最大値を求めよ。

制約条件

h, w≦50
k≦3

方針

現在のマスの周囲のうち、すでに訪れたマスを全部覚えておけばよい。
kが小さいので、二度踏む可能性がある（=覚える必要がある）マスというのは少ない。
具体的には11個以下になる。

なので、dp[i][j][k][bit]を(i, j)にいて、k回戻って、bitで表される周囲のマスに既に入っているときの最大スコアとして、
それを更新してくDPをすればいい。

ソースコード

const int dy[] = {0, 1, 0, -1}, dx[] = {1, 0, -1, 0};
int h, w, K;
string in[50];
int dp[50][50][4][1 << 11];

vector<pi> pos[4];
int trans[1 << 11][4][4];
int vis[1 << 11][4][4];

int main(){
	//kごとに、覚えるべきマスを列挙
	rep(k, 4){
		for(int y = -3; y < 4; y++)
		for(int x = -3; x < 4; x++) if(y || x){
			int yoru = max(x, 0) + max(y, 0);
			int modoru = max(-x, 0) + max(-y, 0);
			//(i, j)まで来る途中にそこに寄り道するのに必要なコスト
			//(i, j)からゴールに行くまでにそこに寄るのに必要なコスト
			//これがどちらもkに関する制約を満たす必要がある
			if(yoru <= k && modoru < 4 - k) pos[k].pb(mp(y, x));
		}
	}
	//移動でビットがどう変わるか
	rep(bit, 1 << 11) rep(k, 4) rep(d, 4){
		
		int nk = k + (d > 1);
		if(nk > 3) continue;
		int &nbit = trans[bit][k][d];
		
		for(int y = -3; y < 4; y++)
		for(int x = -3; x < 4; x++){
			int pp = -1, p = -1;
			int ny = y - dy[d], nx = x - dx[d];
			
			rep(i, pos[k].size()) if(pos[k][i] == mp(y, x)) pp = i;
			rep(i, pos[nk].size()) if(pos[nk][i] == mp(ny, nx)) p = i;
			if(pp < 0 || p < 0) continue;
			if(bit & 1 << pp) nbit |= 1 << p;
		}
		//直前にいたマスにフラグをたてる
		int t = -1;
		rep(i, pos[nk].size()) if(pos[nk][i] == mp(-dy[d], -dx[d])) t = i;
		if(t >= 0) nbit |= 1 << t;

		rep(i, pos[k].size()) if((bit & 1 << i) && pos[k][i] == mp(dy[d], dx[d])) vis[bit][k][d] = 1;
	}
	
	cin >> h >> w >> K;
	rep(i, h) cin >> in[i];
	memset(dp, -1, sizeof(dp));
	
	dp[0][0][0][0] = 0;
	rep(k, K + 1) rep(i, h) rep(j, w) rep(l, 1 << 11) if(dp[i][j][k][l] >= 0){
		
		rep(d, 4){
			int nk = k + (d > 1);
			if(nk > K) continue;
			
			int nxt = dp[i][j][k][l], nl = trans[l][k][d];
			int ny = i + dy[d], nx = j + dx[d];
			if(ny < 0 || ny >= h || nx < 0 || nx >= w || in[ny][nx] == '#') continue;
			
			if(!vis[l][k][d] && in[ny][nx] != '.') nxt += in[ny][nx] - '0';
			dp[ny][nx][nk][nl] = max(dp[ny][nx][nk][nl], nxt);
		}
	}
	int ans = -1;
	rep(i, K + 1) rep(j, 1 << 11) ans = max(ans, dp[h - 1][w - 1][i][j]);
	cout << ans << endl;
	
	return 0;
}

出展

2013年度日本情報オリンピック(JOI)予選