TopCoder SRM 588 Div1 Medium KeyDungeonDiv1

問題

n個のドアがある。
i番目のドアを開けるのに、赤の鍵がdoorR[i]個、緑の鍵がdoorG[i]個必要である。
i番目のドアを開けると、（最初の一回だけ）
赤の鍵がroomR[i]個、緑の鍵がroomG[i]個、白の鍵がroomW[i]個得られる。

一度使った鍵は壊れるのですぐに捨てなければならない。
白の鍵は、赤の鍵または緑の鍵の代わりとして使うことができる。
最初、赤の鍵をkeys[0]個、緑の鍵をkeys[1]個、白の鍵をkeys[2]個持っている。

途中、最大でいくつの鍵を同時に持つことができるか（種類は関係ない）求めよ。

制約条件

n≦12
keys, doorX, roomX≦10

方針

開けたドアの集合と、それまでに使った白の鍵の数を決めると、
今の鍵の個数が一意に定まる。
なのでこれを更新するような探索をすればいい。

ビットは単調増加（開けたドアは減らない）なのでDPで書ける。
今もっている鍵の個数もDPテーブルの値に持たせてしまうと楽。

ソースコード

int n;
pair<int, pi> dp[1 << 12][150];

class KeyDungeonDiv1 {
	public:
	int maxKeys(vector <int> doorR, vector <int> doorG, vector <int> roomR, vector <int> roomG, vector <int> roomW, vector <int> keys) {
		n = doorG.size();
		int ans = keys[0] + keys[1] + keys[2];
		
		rep(i, 1 << n) rep(j, 150) dp[i][j] = mp(-1, mp(0, 0));
		dp[0][0] = mp(keys[0], mp(keys[1], keys[2]));
		
		rep(i, 1 << n) rep(j, 150){
			int r = dp[i][j].first, g = dp[i][j].second.first, w = dp[i][j].second.second;
			if(r < 0) continue;
			
			rep(k, n) if(!(i & 1 << k)){
				int nw = w, nr = r, ng = g, nj = j;
				nw -= max(0, doorR[k] - r); nr = max(0, r - doorR[k]);
				nw -= max(0, doorG[k] - g); ng = max(0, g - doorG[k]);
				
				if(nw < 0) continue;
				nj += w - nw;
				nw += roomW[k];
				nr += roomR[k];
				ng += roomG[k];
				dp[i | 1 << k][nj] = max(dp[i | 1 << k][nj], mp(nr, mp(ng, nw)));
				if(nw + nr + ng > ans) ans = nw + nr + ng;
			}
		}
		return ans;
	}
};