POJ 1065 - Wooden Sticks

http://111qqz.com/2015/03/poj1065/
There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:
(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l' and weight w' if l <= l' and w <= w'. Otherwise, it will need 1 minute for setup.
You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are ( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , and ( 4 , 1 ) , then the minimum setup time should be 2 minutes since there is a sequence of pairs ( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 ) , ( 1 , 2 ) , ( 2 , 5 ) .
Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n , 1 <= n <= 5000 , that represents the number of wooden sticks in the test case, and the second line contains 2n positive integers l1 , w1 , l2 , w2 ,..., ln , wn , each of magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.
Output

The output should contain the minimum setup time in minutes, one per line.
Sample Input

3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1
Sample Output

2
1
3
http://blog.csdn.net/u014688145/article/details/71475303

n根木材长l_i重w_i，前一根木材大于后一根的话要浪费一分钟准备机器，求最省方案？

• 如果只有长度为l[i]的情况下，答案永远都是1。所以关键问题在于两个维度，不能够同时满足L和W分别递增。所以我们能想到的是，尽量去满足一个维度递增，所以对长度L进行排序。
• 每个子序列总能满足长度L和重量W都递增。

求这样的子序列最小值x，该问题等价于按L递增排序后stick按W最长下降子序列的长度h。

这点很关键，现在我们假设木块已经按照长度L递增，现在只关注W的相对顺序。

• x = 1，那么这意味着，w均为递增才能符合这种情况。如果出现一个递减，那么必然不符合。
• x = 2，想象一下，符合递增的放在一个“空位”上，而遇到第一个递减元素，就放在另外一个“空位”上，当出现第三个递减时，不管放在哪两个空位上，也都不符合。

所以我们猜测，x = h，h为L递增后stick按W最长下降子序列的长度。

证明： 
假设存在　x＜h，那么安排x个“容器”，我们知道在该序列中存在h个连续递减的子序列，它们不可能放在一个容器内，所以尽可能的放在每个容器中，但很不幸，由于鸽笼原理，必然会有一对递减序列放在同一个容器中，与命题矛盾。所以必然有x≥h

public static void main(String[] args) { Scanner in = new Scanner(System.in); int T = in.nextInt(); for (int i = 0; i < T; i++){ int n = in.nextInt(); int[] l = new int[n]; int[] w = new int[n]; for (int j = 0; j< n; j++){ l[j] = in.nextInt(); w[j] = in.nextInt(); } System.out.println(solve(l, w)); } in.close(); } public static int solve(int[] l, int[] w){ int n = l.length; Pair[] pairs = new Pair[n]; for (int i = 0; i < n; i++){ pairs[i] = new Pair(l[i],w[i]); } Arrays.sort(pairs, new Comparator<Pair>() { @Override public int compare(Pair o1, Pair o2) { return o1.start != o2.start ? o1.start-o2.start : o1.end - o2.end; } }); int[] dp = new int[n]; int len = 0; for (int i = 0; i < n; i++){ int index = Arrays.binarySearch(dp, 0,len,-pairs[i].end); if (index < 0) index = -(index + 1); dp[index] = -pairs[i].end; if (index == len) len ++; } return len; } class Pair{ int start; int end; Pair(int start, int end){ this.start = start; this.end = end; } @Override public String toString() { return "["+start+","+end+"]"; }