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 (4,9), (5,2), (2,1), (3,5), and (1,4), then the minimum setup time should be 2 minutes since there is a sequence of pairs (1,4), (3,5), (4,9), (2,1), (5,2).

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 n 2 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.

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

Asia 2001, Taejon (South Korea)

题目大意：
有若干组木棍：木棍的长度为I 重为W   现在用机器加工这些木头： 规则如下：

1；加工第一组木头会花去1分钟
2：设加工的下一组木头的长度为 I'  重量为W‘   如果   I=<I' 且 W=<W'  ,则加工这根木头不需要花费时间。

问，所花费的最少时间是多少？


我们可以先把这些木棍进行排序，然后再从顶向下遍历。每次找到最长的增长序列。最后得到的增长序列的个数即为所求的答案。

举个例子： 

4 9 5 2 2 1 3 5 1 4 

排序过后为：
1,4
2,1
3,5
4,9
5,2

然后从上向下扫 ，可以找到两个递增序列。分别是

第一组：1,4  3,5  4,9
第二组：2,1 5,2

这组数据的结果是：2
          
            

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define MM(a) memset(a,0,sizeof(a));struct sticks
{int len,we;bool vis;///vis 用来记录访问情况
}temp[10005];bool cmp(sticks a,sticks b)///先以长度为标准排序。再以重量为标准排序。
{if(a.len==b.len){return a.we<b.we;}else{return a.len<b.len;}
}
int main()
{int t;cin>>t;while(t--){MM(temp);int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d %d",&temp[i].len,&temp[i].we);}sort(temp,temp+n,cmp);int flag=0;int j=0;while(j<n)///从上向下遍历。找到最长的递增序列的{flag++;///flag为最长增长序列的个数int len2=0,we2=0;for(int i=0;i<n;i++){if(temp[i].vis==false){if(temp[i].len>=len2&&temp[i].we>=we2)///满足题意{
//                         printf ("%d %d\n", temp[i].len,temp[i].we);j++;temp[i].vis=true;///标记为以访问len2=temp[i].len;we2 =temp[i].we;}}}}printf("%d\n",flag);}return 0;
}