1787.cpp

来自「自己的ac代码 在acm.zju.edu.cn 上的题目」· C++ 代码 · 共 52 行

#include<stdio.h>
#include<algorithm>
using namespace std;
struct node
{
	int a,b;
};
node p[10005];
bool cmp(node n1,node n2)
{
	if(n1.a<n2.a)return true;
	else if(n1.a==n2.a && n1.b<n2.b) return true;
	else
		return false;
}

int main()
{
	int i,j,k;
	int n;
	int opt[10005];
	int ans;
	while(scanf("%d",&n))
	{
		if(n==0)break;
		for(i=0;i<n;i++)
			scanf("%d%d",&p[i].a,&p[i].b);
		sort(&p[0],&p[n],cmp);
		for(i=0;i<n;i++)
			opt[i]=1;
		ans=1;
		for(i=0;i<n;i++)
			for(j=i+1;j<n;j++)
			{
				if(p[i].b<=p[j].b && opt[i]+1>opt[j])opt[j]=opt[i]+1;
			}
		for(i=0;i<n;i++)
			if(ans<opt[i])ans=opt[i];
		printf("%d\n",ans);
	}
	printf("*\n");
	return 0;
}