先按照一维排序，然后在第二维求最大上升子序列。注意比较的时候还要考虑第一维虽然排序，还是有可能相等的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 |
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;} |
原文：http://www.cnblogs.com/lautsie/p/3528998.html