Source Code

Problem: 3636  User: lianzhouxiaowu 
Memory: 476K  Time: 547MS 
Language: C++  Result: Accepted 

Source Code 
// poj 3636  
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 20005;
struct box{
	int h, w;
}boxs[N], pos[N];
int n;
bool cmp1(box b1, box b2){
	if(b1.h != b2.h) return b1.h < b2.h;
	return b1.w > b2.w;
}

int main(){ 
	int i, t, r, j;
	scanf("%d", &t);
	while(t--){
		scanf("%d", &n);
		for(i = 0; i < n; i++) scanf("%d%d", &boxs[i].w, &boxs[i].h);
		sort(boxs, boxs + n, cmp1);
		//pos记录的是极大元的下标
		r = 0;
		for(i = 0; i < n; i++){
			for(j = 0; j < r; j++){
				if(boxs[i].h > pos[j].h && boxs[i].w > pos[j].w){
					pos[j] = boxs[i];
					break;
				}
			}
			if(j == r) pos[r++] = boxs[i];
		}
		printf("%d\n", r);
	}
	return 0;
}


再看下面这个：

Source Code

Problem: 3636  User: lianzhouxiaowu 
Memory: 400K  Time: 829MS 
Language: C++  Result: Accepted 

Source Code 
// poj 3636  
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 20005;
struct box{
	int h, w;
}boxs[N];
int n;
int pos[N];  
bool cmp1(box b1, box b2){
	if(b1.h != b2.h) return b1.h < b2.h;
	return b1.w > b2.w;
}

int main(){ 
	int i, t, r, j;
	scanf("%d", &t);
	while(t--){
		scanf("%d", &n);
		for(i = 0; i < n; i++) scanf("%d%d", &boxs[i].w, &boxs[i].h);
		sort(boxs, boxs + n, cmp1);
		//pos记录的是极大元的下标
		r = 0;
		for(i = 0; i < n; i++){
			for(j = 0; j < r; j++){
				if(boxs[i].h > boxs[pos[j]].h && boxs[i].w > boxs[pos[j]].w){
					pos[j] = i;
					break;
				}
			}
			if(j == r) pos[r++] = i;
		}
		printf("%d\n", r);
	}
	return 0;
}

//两百多毫秒的差距竟然是因为记录下标和记录元素的不同！！！是不是数组下标的嵌套[[]]会比较慢啊？