Longest Increasing Box

来源：cc150, itint5

原帖：http://www.itint5.com/oj/#34

题目：
有n块积木，每块积木有体积vol和重量weight两个属性，用二元组(vol, weight)表示。积木需要搭成竖直的塔状，上面积木的体积和重量必须都比它下面的积木小。问最多可以搭多少个积木。样例：
有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寻找最长严格递增子序列。

代码：

 /*积木的定义(请不要在代码中定义该结构)  
 struct Box {  
  int vol, weight;  
 };*/  
    
 int mycompare(const Box& a, const 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);  
   vector<int> dp(N, 0);  
   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;  
 }