程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> BZOJ 1107 POI2007 駕駛考試egz LIS

BZOJ 1107 POI2007 駕駛考試egz LIS

編輯:關於C++

題目大意:。。。不是很好敘述自己看吧。注意要剪掉初始就能到達所有終點的點的數量

 

OTZ 這做法實在是太優雅了!

 

#include 
#include 
#include 
#include 
#define M 100100
using namespace std;
struct abcd{
	int pos,val;
	abcd() {}
	abcd(int _,int __):
		pos(_),val(__) {}
}a1[M],a2[M];
int tot1,tot2;
int n,m,p,k,ans;
int l[M],r[M];
bool Compare1(const abcd &x,const abcd &y)
{
	if( x.pos != y.pos )
		return x.pos < y.pos ;
	return x.val < y.val ;
}
bool Compare2(const abcd &x,const abcd &y)
{
	if( x.pos != y.pos )
		return x.pos > y.pos ;
	return x.val < y.val ;
}
struct BIT{
	int c[M];
	void Update(int x,int y)
	{
		for(;x;x-=x&-x)
			c[x]=max(c[x],y);
	}
	int Get_Ans(int x)
	{
		int re=0;
		for(;x<=m;x+=x&-x)
			re=max(re,c[x]);
		return re;
	}
}b1,b2;
int main()
{
	int i,j,x,y,z;
	cin>>n>>m>>p>>k;++m;
	for(i=1;i<=p;i++)
	{
		scanf(%d%d%d,&x,&y,&z);++y;
		if(z)
			new (&a1[++tot1])abcd(x+1,y);
		else
			new (&a2[++tot2])abcd(x,y);
	}
	sort(a1+1,a1+tot1+1,Compare1);
	sort(a2+1,a2+tot2+1,Compare2);
	l[0]=r[n+1]=-1;
	for(j=1,i=1;i<=n;i++)
	{
		l[i]=l[i-1]+1;
		for(;j<=tot1&&a1[j].pos==i;j++)
		{
			int temp=b1.Get_Ans(a1[j].val)+1;
			l[i]=min(l[i],(i-1)-temp);
			b1.Update(a1[j].val,temp);
		}
	}
	for(j=1,i=n;i;i--)
	{
		r[i]=r[i+1]+1;
		for(;j<=tot2&&a2[j].pos==i;j++)
		{
			int temp=b2.Get_Ans(a2[j].val)+1;
			r[i]=min(r[i],(n-i)-temp);
			b2.Update(a2[j].val,temp);
		}
	}
	for(j=1,i=1;i<=n;i++)
	{
		for(;i-j+1&&l[i]+r[j]>k;j++);
		ans=max(ans,i-j+1);
	}
	for(i=1;i<=n;i++)
		if(!l[i]&&!r[i])
			--ans;
	cout<

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved