4563559_ce.cpp

部分PKU上的源码

#include<iostream>
#include<algorithm>
using namespace std;
struct wood
{
	int l;
	int w;
};
wood x[5000];
int next[5000];
int pre[5000];
int kai[5000];
int testnumber;
int number;
int result;
int compare(int a,int b)
{
	if(x[a].w>x[b].w&&x[a].l>x[b].l) return 1;
	if(x[a].w<x[b].w&&x[a].l<x[b].l) return 2;
	if(x[a].w==x[b].w&&x[a].l==x[b].l) return 3;
	else return 4;
}
void in(int now)
{
	//bool can=false;
	for(int count=0;count<result;count++)
	{
		int temp=kai[count];
		while(temp!=-1)
		{
			bool can=false;
			switch(compare(now,temp))
			{
			case 1:if(next[temp]==-1){next[temp]=now;pre[now]=temp;return;}
				else temp=next[temp];break;
			case 2:if(pre[temp]!=-1) {next[pre[temp]]=now;pre[now]=pre[temp];next[now]=temp;pre[temp]=now;}
				else {next[now]=temp;pre[temp]=now;}
				return;
			case 3:can=true;return;
			case 4:can=true;break;
			}
			if(can) break;
		}
	}
	if(count==result) {result++;kai[result-1]=now;}
}
void deal()
{
	memset(next,-1,sizeof(next));
	memset(kai,0,sizeof(kai));
	memset(pre,-1,sizeof(pre));
	cin>>number;
	result=0;
	for(int count=0;count<number;count++)
	{
		cin>>x[count].l>>x[count].w;
		in(count);
	}
	cout<<result<<endl;
}
void main()
{
	cin>>testnumber;
	for(int count=0;count<testnumber;count++)
		deal();
}