//5340K 313MS Java
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Comparator;
import java.util.Arrays;
public class Main {
private static final int MAX = 5000;
private class Stick implements Comparable{
public int mLength;
public int mWeight;
public Stick(int length, int weight) {
mLength = length;
mWeight = weight;
}
public int compareTo(Object o) {
// int lenthCmpRes = this.mLength - ((Stick)o).mLength;
int lenthCmpRes = this.mLength - ((Stick)o).mLength;
return lenthCmpRes != 0 ? lenthCmpRes :
this.mWeight - ((Stick)o).mWeight;
}
}
private class StickComparator implements Comparator<Stick> {
@Override
public int compare(Stick o1, Stick o2) {
int lengthCmpRes = o1.mLength - o2.mLength;
return lengthCmpRes != 0 ? lengthCmpRes:
o1.mWeight - o2.mWeight;
}
}
private StickComparator mComparator;
private Stick[] Sticks;
private byte[] flag;
private int mCurStickInsertPos;
public void addStick(int length, int weight) {
Sticks[mCurStickInsertPos++] = new Stick(length, weight);
}
public void getMinSetupTime() {
Arrays.sort(Sticks, 0, mCurStickInsertPos, mComparator);
int setupTime = 0;
for (int i = 0; i < mCurStickInsertPos; i++) {
if (flag[i] == 0) { // if not handled yet
// System.out.println(i);
setupTime++;
int curWeight = Sticks[i].mWeight;
flag[i] = 1;
for (int j = i+1; j < mCurStickInsertPos ;j++) {
if (curWeight <= Sticks[j].mWeight && flag[j] == 0) {
curWeight = Sticks[j].mWeight;
flag[j] = 1;
// System.out.println(Sticks[j].mLength + " " + Sticks[j].mWeight);
}
}
}
}
System.out.println(setupTime);
}
public Main() {
mCurStickInsertPos = 0;
flag = new byte[MAX];
Sticks = new Stick[MAX];
mComparator = new StickComparator();
}
public void reset() {
for (int i = 0; i < MAX; i++) {
flag[i] = 0;
}
mCurStickInsertPos = 0;
}
public static void main(String[] args) {
Main solver = new Main();
Scanner input = new Scanner(System.in);
int caseNum = input.nextInt();
for (int i = 0; i < caseNum; i++) {
solver.reset();
int stickNum = input.nextInt();
for (int j = 0; j < stickNum; j++) {
int length = input.nextInt();
int weight = input.nextInt();
solver.addStick(length, weight);
}
solver.getMinSetupTime();
}
}
}//5340K 313MS Java
贪心水题，不过却犯了不少乌龙。。。
首先是把题目的大小比较给看错了，原题是后面的stick的l和w都比前一个长才不用花时间setup，我给看反了，而两个例子在这种情况下答案也一样，看不出错...
然后是理解偏差，一个l1w2的stick在接着处理了一个4l5w的stick以后，l和w要按照最近处理的stick来参考，比如这时候，3l4w的stick就需要setup时间了. 一开始
给理解成只要能接着处理，l和w都按第一个stick的来取。
使用java本身也出了不少语言错误，java还是要多练练，POJ还要求class必须是"Main"
除去这些，题本身求解倒不难，
为了熟悉java的数组排序，这里没有用最快的方法，不过这道题对时间也不敏感。
思路是这样的，一开始按照l或者w来进行升序排序，得到一个有序的stick数组S（这里假设按照L升序排序）。
还要维护一个stick的flag数组，标示此stick是否被处理过了。
然后从S的第一个成员A开始，setupTime要+1， 取得该成员的L和W，那么对L来说，A后面所有stick的L都>=L（升序），因此L不用管了，
而W因为没有经过排序，因此要向后遍历，只要找到>=W的stick，就是可以不需要setupt时间的stick，同时在flag中标示此stick已经被处理了。
同时W要更新为这个stick的W，一直向后，直到遍历完S。
至此以A为开始的不需要额外setuptime的序列就完了，接下来，要找下一个还没有被处理的stick，作为新一轮没有额外setuptime序列的起始stick，
然后重复上面的过程，直到所有的stick都被处理完，
至此得到的setuptime就是最小的。
更效率的办法是每个L都维护一个自己的W升序序列（其实就是排序时，L相等的情况下，再考虑W），这样在对于某个L的stick序列，查找对于某个W能够不需要额外setup时间的stick就可以很快得到。
其实我不怎么喜欢贪心法，对于一些直观的题还好，但是对于某些题，
如何得到贪心的解以及证明贪心是最好的，这个过程其实没有一个统一的流程（和DP不一样），更偏向于一种直觉和智力上的挑战，
对于我这样的普通人来说，是很难学来的.
至于本题的贪心证明，先贴一个别人的证明:
其实这题需要两次贪心
初始思路，
最长不降子序列或者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
自己的理解：
从直觉上想，如果我们不按照L或者W的升序顺序来进行操作，比如 不从L1（最小的L的stick群）开始，而是从L2（第2小L的stick群）开始，那样，后面不管怎么做，L1的stick群都不可能在本次没有额外的setup的前提下被处理（因为L永远>= L2 ），必然会比从L1开始额外的增加一次setup（从L2开始绝不对比从L1开始需要额外的setup time），这样基本证明了从L1开始是最好的，
然后是在从某个LN集群开始处理，在L确定情况下，当然是能够在不增加setup time的前提下处理越多的stick越好，这个证明其实是显而易见的。
这个证明还是不够规范，不是严格的数学推理，贪心相对于DP的优势就在于从上到下，效率高。