3312991_ac_32ms_340k.cpp

部分PKU上的源码

#include<iostream>
#include <algorithm>
using namespace std;
struct wooden
{int length,width;
};
wooden x[5000],test[5000];

int t,i,j,k,m,n,result;
int get(int n)
{result=1;test[0]=x[0];
	for(k=1;k<n;k++)
	{
		for(m=0;m<result;m++)
		{
			if((x[k].length>=test[m].length)&&(x[k].width>=test[m].width)) break;
		}
		test[m].length=x[k].length;test[m].width=x[k].width;
		if(m==result) result++;
	}
	return result;
}





int compare(const wooden &m1,const wooden &m2)
{
	if(m1.length<m2.length) return 1;
	if(m1.length>m2.length) return 0;
	else 
	{
		if(m1.width<m2.width) return 1;
		if(m1.width>m2.width) return 0;
		else return 0;
	}
}
	
int main()
{
	cin>>t;
	for(i=0;i<t;i++)
	{
		cin>>n;
	    for(j=0;j<n;j++) cin>>x[j].length>>x[j].width;
		sort(x,x+n,compare);
		cout<<get(n);
		if(i!=t) cout<<endl;
	}
	return 1;
}