TopCoder SRM 310 Div1 Hard BoxTower

問題

n個の直方体の箱があり、それぞれの高さ、幅、奥行きがわかっている。
この箱のうち、好きなものを選び積み上げて塔を作る。


塔は、それぞれの箱を軸に平行に置かねばならず、
箱の底面は、一つ前の箱の底面からはみでてはならない。
箱は自由な向きで使えるとしたとき、できる塔の高さの最大値を求めよ。

制約条件

n≦15
大きさ≦10^7とか

方針

dp[どの箱を使ったか][最後の箱][その向き]
を更新するO(2^n * n^2)のDP.
Hardが今のMediumより簡単な時代だったらしい。やるだけ。

ソースコード

int n, dp[1 << 15][16][3];

class BoxTower {
	public:
	int tallestTower(vector <int> x, vector <int> y, vector <int> z) {
		n = x.size();
		memset(dp, -1, sizeof(dp));
		
		x.pb(inf); y.pb(inf); z.pb(inf);
		
		int ans = 0;
		dp[0][n][0] = 0;
		rep(i, 1 << n) rep(j, n + 1) rep(k, 3) if(dp[i][j][k] >= 0){
			
			int a, b, c, d, e;
			if(k == 0) a = x[j], b = y[j];
			else if(k == 1) a = x[j], b = z[j];
			else a = y[j], b = z[j];
			
			if(a > b) swap(a, b);
			
			rep(l, n) if(!(i & 1 << l)) rep(m, 3){
				if(m == 0) c = x[l], d = y[l], e = z[l];
				else if(m == 1) c = x[l], d = z[l], e = y[l];
				else c = y[l], d = z[l], e = x[l];
				
				if(c > d) swap(c, d);
				
				if(a >= c && b >= d){
					dp[i | 1 << l][l][m] = max(dp[i | 1 << l][l][m], dp[i][j][k] + e);
					ans = max(ans, dp[i][j][k] + e);
				}
			}
		}
		return ans;
	}
};