AOJ 0234 - Aizu Buried Treasure

問題文 : 会津の埋蔵金

解法 :
f(ny, nx, l, r, oxygen) -> 現在場所(nx, ny)にいて, 深さny[m]のうちl ~ rまでの距離は移動済みで, oxygenだけ酸素をもっている, という状態をもった動的計画法を行う.
状態空間が5*10^4になるため, 楽にメモ化再帰ができる.
最初に穴を掘るときに酸素が1しかないとすぐに酸素が補給できなくなることに注意.

コード :

#include <cmath>
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>

using namespace std;

int memo[10][10][10][10][51];
int mp[10][10];
int W, H;
int M, Olim, O;

int search(int ny, int nx, int l, int r, int ox)
{
	if (ox <= 0) return (INT_MAX / 2);
	if (ny == H - 1) return (0);
	if (memo[ny][nx][l][r][ox] >= 0) return (memo[ny][nx][l][r][ox]);
	
	int m, o;
	int res = INT_MAX / 2;
	
	if (ox == 1) return (INT_MAX / 2);
	
	if (nx > 0){
		m = o = 0;
		if (l > nx - 1){
			if (mp[ny][nx - 1] < 0) m = -mp[ny][nx - 1];
			else o = mp[ny][nx - 1];
		}
		res = min(res, search(ny, nx - 1, min(l, nx - 1), r, min(Olim, ox + o - 1)) + m);
	}
	
	if (nx < W - 1){
		m = o = 0;
		if (nx + 1 > r){
			if (mp[ny][nx + 1] < 0) m = -mp[ny][nx + 1];
			else o = mp[ny][nx + 1];
		}
		res = min(res, search(ny, nx + 1, l, max(r, nx + 1), min(Olim, ox + o - 1)) + m);
	}
	
	m = o = 0;
	if (mp[ny + 1][nx] < 0) m = -mp[ny + 1][nx];
	else o = mp[ny + 1][nx];
	res = min(res, search(ny + 1, nx, nx, nx, min(Olim, ox + o - 1)) + m);
	
	return (memo[ny][nx][l][r][ox] = res);
}

int main()
{
	while (scanf("%d %d", &W, &H) && W){
		scanf("%d %d %d", &M, &Olim, &O);
		
		for (int i = 0; i < H; i++){
			for (int j = 0; j < W; j++){
				scanf("%d", &mp[i][j]);
			}
		}
		
		int a = INT_MAX / 2;
		
		memset(memo, -1, sizeof(memo));
		for (int i = 0; i < W; i++){
			if (O <= 1) break;
			int m = 0, o = 0;
			if (mp[0][i] < 0) m = -mp[0][i];
			else o = mp[0][i];
			a = min(a, search(0, i, i, i, min(Olim, O + o - 1)) + m);
		}
		
		if (a == INT_MAX / 2 || a > M) printf("NA\n");
		else printf("%d\n", a);
	}
	
	return (0);
}