SSOJ2346零件分组
5186+
作者：crxis 发布：2017-07-07 分类：贪心
题目大意：有n个零件，都有一定长度和重量，至少分几组，才能使每一组零件都能排成一个长度和重量都不下降的序列？
题目描述
某工厂生产一批棍状零件，每个零件都有一定长度（Li）和重量（Wi）。现在为了加工需要，要将它们分成若干组，使每一组的零件都能排成一个长度和重量都不下降（若i<j，则Li<=LJ,Wi<=Wj）的序列。请问至少要分成几组？
输入
第一行：一个整数n（n<=1000），表示零件的个数
第二行：n对正整数，每队正整数表示这些零件的长度与重量，长度与重量均不超过10000，两个数之间用一空格隔开
输出
仅一行，即最少分成的组数
样例输入
5
8 4 3 8 2 3 9 7 3 5
样例输出
2
解题思路
先排序：按照长度排序，长度相同按重量排序，小的在前。这样，逐个对零件进行分组，保证长度不递减，下面讨论如何保证重量不递减。
对于每个零件，要么放到新的一组，要么放到之前的分组。首先，看一下能不能放在之前的分组，即看一下之前的分组中最重的零件是否有不重过这个零件的，如果没有，则必须新开一组；有的话，零件放在能放这个零件的组中的最重零件最重的那组，保证当前最优。最后输出分组数量即可。
其实，去除长度影响后，分组只需要看重量，可以转换成求重量的最长下降子序列的长度。
程序实现
