其实这题需要两次贪心

初始思路，
最长不降子序列或者floyd求最长路，floyd肯定超时，写nlogn的最长不降子序列也非常蛋疼

于是，
第一次贪心：其实并非每次都要求一个最长的序列，然后删除，只要选出的序列符合"极大"即可。这里的极大和函数的极值是一个概念。
例如，(1,4) (4,4) (5,3) (9,4) 其中最大(最长)的一个序列为 (1,4)->(4,4)->(9,4)
极大的序列 为 (5,3)->(9,4)
证明：很简单，因为所有的木头都需要被加工，并且与加工的先后顺序无关，那么该木头一定
需要在某个序列中，而我们每次选择的序列是极大的，故每次操作都没有遗漏可加入的木头，因此总的操作数是最少的。

第二次贪心：得到一个极大的序列，直接枚举的复杂度是O(n^3)，显然超时。进一步思考

考虑任意的序列：对于任意的序列(a,b)->(c,d) 如果该序列是合法的，那么必然满足
a<=c 且 b<=d ，不等式相加可得 a+c<=b+d

上面的不等式提示我们，对于任意的合法序列，必然满足长度与重量之和 是不降的

因此，如果我们将长度作为第一关键字，重量做为第二关键字进行升序排序，那么从左到右，选取所有w不降的序列，则该序列必然是极大序列。

证明：1.序列是合法的，这个正确性显然。2.序列是极大的，因为我们在1的前提下，尽可能多的选取木头

于是我们得到了最终的算法：O(nlgn+n^2)

1.先按第一关键字排序，若第一关键字相等，则按第二关键字排序
2.找出w不降，且未被标记的所有木头，将之标记
3.直到所有的木棍都被标记，否则继续执行2

• Re:给个简单证明吧 (135) Mandolin23 2011-04-14 05:44:01
• Re:给个简单证明吧 (10) hongxingxiaonan 2012-06-15 18:36:32
• 懂了，感谢大佬 (2) 1813382441 2020-02-12 13:01:30