SRM588 D1-Medium KeyDungeonDiv1

問題

n個の部屋からなるダンジョンがある。i番目の部屋に入るためには赤い鍵がdoorR[i]個と緑色の鍵がdoorG[i]個必要となる。ただし、白い色のカギがある場合はそれを赤い鍵または緑色の鍵の代わりとして使用することができる。また、扉を開けるのに使用した鍵はそれ以降使用できなくなる。
i番目の部屋の鍵を開けた際、赤・緑・白の鍵がそれぞれroomR[i], roomG[i], roomW[i]個新たに手に入る。
最初に赤・緑・白の鍵がそれぞれkeys[0], keys[1], keys[2]個与えられたとき、手元に残すことのできる鍵の数の最大値を求めよ。（すべての扉を開ける必要はない）

• n <= 12
• doorR[i], doorG[i], roomR[i], roomG[i], roomW[i], keys[i] <= 10

解法

動的計画法で解く。
dp[扉の開閉状況(ビット集合)][赤い鍵の代わりに使った白い鍵の数] = max(手元に残っている白い鍵の数)

コード

int dp[1 << 12][140];

class KeyDungeonDiv1 {
public:
	int maxKeys(vector<int> doorR, vector<int> doorG, vector<int> roomR, vector<int> roomG, vector<int> roomW, vector<int> keys){
		const int n = doorR.size();
		memset(dp, -1, sizeof(dp));
		dp[0][0] = keys[2];
		for(int i = 0; i < (1 << n); ++i){
			for(int j = 0; j < 140; ++j){
				if(dp[i][j] < 0){ continue; }
				int r = keys[0], g = keys[1], w = keys[2];
				for(int k = 0; k < n; ++k){
					if((i & (1 << k)) == 0){ continue; }
					r += roomR[k] - doorR[k];
					g += roomG[k] - doorG[k];
					w += roomW[k];
				}
				r += j;
				g += w - j - dp[i][j];
				w = dp[i][j];
				for(int k = 0; k < n; ++k){
					if((i & (1 << k)) != 0){ continue; }
					const int next = i | (1 << k);
					for(int l = 0; l <= doorR[k]; ++l){
						if(l > w){ continue; }
						if(doorR[k] - l > r){ continue; }
						const int tw = w - l;
						const int gw = max(doorG[k] - g, 0);
						if(gw > tw){ continue; }
						const int tw2 = tw - gw + roomW[k];
						dp[next][j + l] = max(dp[next][j + l], tw2);
					}
				}
			}
		}
		int answer = 0;
		for(int i = 0; i < (1 << n); ++i){
			for(int j = 0; j < 140; ++j){
				if(dp[i][j] < 0){ continue; }
				int sum = keys[0] + keys[1] + keys[2];
				for(int k = 0; k < n; ++k){
					if((i & (1 << k)) == 0){ continue; }
					sum -= doorR[k] + doorG[k];
					sum += roomR[k] + roomG[k] + roomW[k];
				}
				answer = max(answer, sum);
			}
		}
		return answer;
	}
};