《Cracking the Coding Interview》——第9章:递归和动态规划——题目10

时间:2022-05-18 16:22:54

2014-03-20 04:15

题目:你有n个盒子,用这n个盒子堆成一个塔,要求下面的盒子必须在长宽高上都严格大于上面的。如果你不能旋转盒子变换长宽高,这座塔最高能堆多高?

解法:首先将n个盒子按照长宽高顺序排好序,然后动态规划,我写了个O(n^2)时间复杂度的代码。

代码:

 // 9.10 A stack of n boxes is form a tower. where every stack must be strictly larger than the one right above it.
// The boxes cannot be rotated.
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std; struct Box {
// width
int w;
// height
int h;
// depth
int d;
Box(int _w = , int _h = , int _d = ): w(_w), h(_h), d(_d) {}; bool operator < (const Box &other) {
if (w != other.w) {
return w < other.w;
} else if (h != other.h) {
return h < other.h;
} else {
return d < other.d;
}
};
}; int main()
{
int n, i, j;
Box box;
vector<Box> v;
vector<int> dp;
int result; while (scanf("%d", &n) == && n > ) {
v.resize(n);
for (i = ; i < n; ++i) {
scanf("%d%d%d", &v[i].w, &v[i].h, &v[i].d);
}
sort(v.begin(), v.end());
dp.resize(n);
for (i = ; i < n; ++i) {
dp[i] = v[i].h;
}
for (i = ; i < n; ++i) {
for (j = ; j < i; ++j) {
if (v[i].w > v[j].w && v[i].h > v[j].h && v[i].d > v[j].d) {
dp[i] = v[i].h + dp[j] > dp[i] ? v[i].h + dp[j] : dp[i];
}
}
}
result = dp[];
for (i = ; i < n; ++i) {
result = dp[i] > result ? dp[i] : result;
}
v.clear();
dp.clear();
printf("%d\n", result);
} return ;
}