TopCoder SRM 580 Div2 Hard WallGameDiv2

Div1 Hardを簡単にした問題。こちらは割と簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=12579

問題

２次元状にセルが並べられたボードを用いてゲームを行う。
各セルは、到達不能であるか、到達可能な場合セルに与えられたコスト(0-9)がかかる。

ここで、最初左上にあるトークンが同一セルを複数回通らないように左・右・下のいずれかの移動を繰り返し、最下段に行くことを考える。
このとき、セルとセルの間に壁を設けて移動不可にすることができる場合、トークンが最下段に行くときの総コストを最大化し、その総コストを答えよ。
ただし、最下段に行くルートをすべて壁でふさぐことはできない。

解法

コストを最大化するには、横にできるだけ移動させればよい。
よって横移動を壁でふさぐ意味はなく、縦移動だけ壁でふさぐことで下に降りれる位置まで横移動させることになる。

ここで、「壁でふさいでコストを最大化」と考えるとややこしいが、結局この問題は「左右と下方向だけで進んで得られるコストを最大化する」と考えることができる。
よって各行において、横移動してその総コストを求め、そして次の行に行く、とDPを行えばよい。
O(N^3)なのでN=50でも余裕。

以下のコードは到達不能なセルのコストを1<<20と置いている。

class WallGameDiv2 {
	int W,H;
	int RC[60];
	int C[60][60];
	public:
	int play(vector <string> costs) {
		int i,x,y,x1,x2;
		W=costs[0].size();
		H=costs.size();
		
		FOR(y,H) FOR(x,W) C[y][x]=-1<<20;
		C[0][0]=0;
		
		for(y=0;y<H-1;y++) {
			RC[0]=0;
			for(x=0;x<W;x++) RC[x+1]=RC[x]+(costs[y][x]=='x'?(1<<20):(costs[y][x]-'0'));
			FOR(x1,W) FOR(x2,W) {
				if(C[y][x1]<0) continue;
				if(costs[y+1][x2]=='x') continue;
				if(x1<=x2 && RC[x2+1]-RC[x1+1]<(1<<20)) C[y+1][x2]=max(C[y+1][x2],C[y][x1]+RC[x2+1]-RC[x1+1]+costs[y+1][x2]-'0');
				if(x1>x2 && RC[x1]-RC[x2]<(1<<20)) C[y+1][x2]=max(C[y+1][x2],C[y][x1]+RC[x1]-RC[x2]+costs[y+1][x2]-'0');
			}
		}
		
		int ma=0;
		FOR(x,W) ma=max(ma,C[H-1][x]);
		return ma;
	}
};

まとめ

Div2 Hardにしては簡単な問題。
Dashboard - Round 2 2009 - Google Code Jam
を簡単にしたような問題。