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; } };