零件分组(stick)

某工厂生产一批棍状零件，每个零件都有一定的长度（Li）和重量（Wi）。现在为了加工需要，要将它们分成若干组，使每一组的零件都能排成一个长度和重量都不下降（若i<j，则Li<=Lj，Wi<=Wj）的序列。请问至少要分成几组?

输入

第一行为一个整数N（N<=1000），表示零件的个数。第二行有N对正整数，每对正整数表示这些零件的长度和重量，长度和重量均不超过10000。

输出

仅一行，即最少分成的组数。

样例

STICK.IN

8 4 3 8 2 3 9 7 3 5

STICK.OUT

 1 #include <iostream>
 2 #include <memory.h>
 3 #include <stdio.h>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 typedef pair<int,int> Group;
 8 Group group[1000];
 9 int flag[1000];///
10 int greedy(int cnt){
11     int count = cnt;
12     int num_group = 0;
13     int mid;
14     memset(flag,0,sizeof(flag));
15         for(int i = 0; i < cnt; i++){
16             if(flag[i] == 0){
17                 ///查找以该元素为起点，依次递增的元素
18                 for(int j = i + 1,mid = i; j < cnt; j++){
19                     if(flag[j] == 1)
20                         continue;
21                     if(group[j].first >= group[mid].first && group[j].second >= group[mid].second){
22                         flag[j] = 1;
23                         mid = j;
24                     }
25                 }
26                 num_group++;
27             }
28         }
29     return num_group;
30 }
31 
32 int main(void){
33     int cnt;/// 零件个数
34     while(scanf("%d",&cnt) != EOF){
35         for(int i = 0; i < cnt; i++){
36             scanf("%d%d",&group[i].first,&group[i].second);
37         }
38         sort(group,group + cnt);
39         printf("%d
",greedy(cnt));
40     }
41     return 0;
42 }