#include <iostream>
using namespace std;

typedef struct {
	int len;
	int wid;
}item;
item  wood[5000];
item  queue[5000];

int compare(const void *a, const void *b){
 return (*((item *)b)).len +(*((item *)b)).wid -(*((item *)a)).len -(*((item *)a)).wid;	
}
int main(){
	//freopen("test.txt","r",stdin);
    int kase,i,j,n,queuelen,find;
    scanf("%d",&kase);
	while(kase--){
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d%d",&wood[i].len,&wood[i].wid);
		}
		qsort(wood,n,sizeof(item),compare);  //sort decreasely by sum of len and wid		
        queuelen=0;
		queue[0]=wood[0];
		for(i=1;i<n;i++){
			find=0;
			for(j=0;j<=queuelen;j++){
				if(wood[i].len<=queue[j].len && wood[i].wid<=queue[j].wid){
					find=1;
					queue[j]=wood[i];
					break;
				}				
			}
			if(!find) {
					queue[++queuelen]=wood[i];
				}
		}		
        printf("%d\n",queuelen+1);
	}
	return 0;
}

• 虽然跟很多人的贪心不太一样，但是我认为这个算法还是没错的吧？？！ (1007) Basara 2006-08-11 12:49:14