## Friday, November 27, 2015

### [itint5]堆放积木 - 阿牧遥 - 博客园

[itint5]堆放积木 - 阿牧遥 - 博客园
http://lixinzhang.github.io/itint5-mian-shi-ti-zong-jie.html

积木需要搭成竖直的塔状，上面积木的体积和重量必须都比它下面的积木小。问最多可以搭多少个积木。
样例：
有7个积木boxes:
[(65, 100), (70, 150), (56, 90), (75, 190), (60, 95), (68, 110), (80, 12)]
最多可以搭6个积木，从上到下分别为：
(56, 90), (60, 95), (65, 100), (68, 110), (70, 150), (75, 190)
所以函数应该返回6。
题目来源：CRACKING THE CODING INTERVIEW 9.7

Solution: 先按照vol进行排序，题目就变成了根据weight寻找最长严格递增子序列。

int mycompare(Box a, Box b) {
if (a.vol == b.vol)
return a.weight < b.weight;
return a.vol < b.vol;
}
int maxBoxes(vector<Box> &boxes) {
int N = boxes.size();
if (N == 0) return 0;
sort(boxes.begin(), boxes.end(), mycompare);
int dp[N];
int res = 1;
for (int i = 0; i < N; ++i)
{
dp[i] = 1;
for (int j = 0; j < i; ++j)
if (boxes[i].vol > boxes[j].vol && boxes[i].weight > boxes[j].weight)
dp[i] = max(dp[i], dp[j] + 1);
res = max(res, dp[i]);
}
return res;
}
`bool` `comp(``const` `Box &a, ``const` `Box &b) {`
`    ``if` `(a.vol != b.vol) {`
`        ``return` `a.vol < b.vol;`
`    ``} ``else` `{`
`        ``return` `a.weight < b.weight;`
`    ``}`
`}`

`/*积木的定义(请不要在代码中定义该结构)`
`struct Box {`
`  ``int vol, weight;`
`};*/`
`int` `maxBoxes(vector<Box> &boxes) {`
`    ``sort(boxes.begin(), boxes.end(), comp);`
`    ``int` `size = boxes.size();`
`    ``int` `max = 0;`
`    ``vector<``int``> dp(size);`
`    ``for` `(``int` `i = 0; i < boxes.size(); i++) {`
`        ``dp[i] = 0;`
`        ``for` `(``int` `j = 0; j < i; j++) {`
`            ``if` `(boxes[j].weight < boxes[i].weight`
`               ``&&boxes[j].vol < boxes[i].vol) {`
`                ``if` `(dp[j] > dp[i]) dp[i] = dp[j];`
`            ``}`
`        ``}`
`        ``dp[i]++;`
`        ``if` `(dp[i] > max) max = dp[i];`
`    ``}`
`    ``return` `max;`
`}`

```/*积木的定义(请不要在代码中定义该结构)
struct Box {
int vol, weight;
};*/

bool cmp(Box b1, Box b2){
return b1.vol < b2.vol;
}

bool isvalid(Box & b1, Box & b2){
return (b1.weight > b2.weight)
&& (b1.vol > b2.vol);
}

int maxBoxes(vector<Box> &boxes) {
if(boxes.size() <=1 ) return boxes.size();
sort(boxes.begin(), boxes.end(), cmp);
vector<int> f(boxes.size(), 1);
f[0] = 1;
int res = 1;
for(int i=1; i<f.size(); i++){
for(int j=0; j<i; j++){
f[i] = max(f[i], isvalid(boxes[i], boxes[j]) ? f[j]+1 : 0);
}
res = max(res, f[i]);
}
return res;
}```