AOJ Problem 0234 : Aizu Buried Treasure

すごくたすかる助言によって通ったので書きます。

>o は 3 以上 m 以下の整数とします

このときなぜか2以下が含まれてる

だそうなので、これだけ対策したら通りました。

問題文:404 Not Found

さて本題。

H,Wは<=10以下ですが、掘った箇所を記録する際、2^(H*W)の状態数を持つとそれだけで余裕で死にます。

どうすればいいかっていうと、上には戻れないって条件があるので、各高さについての横の移動した範囲とかだけで十分であることが分かります。

この時bitで2^Wの状態を持ってもいいんですが、各地層は横で見ると必ず連続した領域でしか掘れないので、各層で、行ったことのある左側の地層と右側の地層で持つと、10*10ですみます。(実際はl>rになることはないので使わない配列もある。)

あとはdijkstraやら動的計画法やらして通します。

この時の状態ノードは[現在のy][現在のx][行った左端][行った右端][酸素]で持ちます。dpも同様です。

詳しくはpckのサイトを見るといいと思います。解説上がってるので。

ちなみに僕、本選では探索空間を減らす発想とか考える余裕無くて死にました。悲しいですね。

ソース

/*
	AOJ 0234 - Problem I: 会津埋蔵金
	http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0234&lang=jp
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF (1<<30)

struct NODE{
	int cost,x,y,l,r,o;
	NODE(int C,int a,int b,int c,int d,int e){cost = C,x=a,y=b,l=c,r=d,o=e;}
};
bool operator<(const NODE& a,const NODE& b){
	return a.cost > b.cost;
}

// 書き込み用変数O,Cと、酸素情報,マスのデータ,酸素制限(=m)を指定すると、添え字に使う酸素と加算するコストをそれぞれ代入してくれる。
int get(int &O,int &C,int s,int d,int lim){
	if(d<0){
		O = s;
		C = -d;
	}else{
		O = min(lim,s + d);
		C = 0;
	}
}

int solve(int W,int H,int m,int o,vector<vector<int> >data){
	if(o<2)return INF;
	int O,C;
	bool done[10][10][10][10][51] = {0}; // [x][y][l][r][o]
	priority_queue<NODE> Q;
	rep(i,W){
		get(O,C,o-1,data[0][i],m);
		Q.push(NODE(C,i,0,i,i,O));
	}
	while(Q.size()){
		NODE q = Q.top(); Q.pop();
		if(q.o == 0) continue;
		if(q.y == H-1) return q.cost;
		
		if(done[q.x][q.y][q.l][q.r][q.o])continue;
		else done[q.x][q.y][q.l][q.r][q.o] = true;
		
		// 残り酸素が1ならば移動できないのでcontinue
		if(q.o == 1) continue;
		
		//横移動
		static const int dx[] = {-1,1};
		rep(i,2){
			int tx = q.x+dx[i];
			int l = min(q.l,tx) , r = max(q.r,tx);
			if(tx < 0 || tx >= W) continue;
			
			if(l == q.l && r == q.r) C = 0 , O = q.o-1 ;
			else get(O,C,q.o-1,data[q.y][tx],m);
			
			Q.push(NODE(q.cost+C,tx,q.y,l,r,O));
		}
		
		//縦移動
		if(q.y < H-1){
			get(O,C,q.o-1,data[q.y+1][q.x],m);
			Q.push(NODE(q.cost+C,q.x,q.y+1,q.x,q.x,O));
		}
	}
	return INF;
}

int main(){
	int W,H,f,m,o;
	while(cin >> W >> H , W){
		cin >> f >> m >> o;
		vector< vector<int> > data(H,vector<int>(W));
		rep(i,H)rep(j,W)cin >> data[i][j];
		int ans = solve(W,H,m,o,data);
		if(ans <= f) cout << ans << endl;
		else cout << "NA" << endl;
	}
}

おまけ:適当な汚いDP

http://ideone.com/L0UM9