hdoj1025

LIS+单调队列优化

#include<stdio.h>
#include<algorithm>
#define N 100000+10
#define inf 1000000000
using namespace std;
typedef struct Node{
	int p,r;
}Node;
Node node[N];
int b[N];
bool cmp(Node a,Node b)
{
	return a.p<b.p;
}
int main()
{
	int i,j;
	int n,cases=0;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++)
		{
			int p,r;
			scanf("%d %d",&p,&r);
			node[i].p=p;
			node[i].r=r;
			b[i]=inf;
		}
		sort(node+1,node+1+n,cmp);
		for(i=1;i<=n;i++)
		{
			int* index=lower_bound(b+1,b+1+n,node[i].r);
			b[index-b]=node[i].r;
		}
		for(i=n;i>=1;i--)
			if(b[i]!=inf)
				break;
		printf("Case %d:\nMy king, at most %d %s can be built.\n\n",++cases,i,i==1?"road":"roads");

	
	}

	//system("pause");
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>