bzoj 1664: [Usaco2006 Open]County Fair Events 参加节日庆祝【dp+树状数组】

把长度转成右端点，按右端点排升序，f[i]=max(f[j]&&r[j]<l[i])，因为r是有序的，所以可以直接二分出能转移的区间(1,w)，然后用树状数组维护区间f的max，每次转移的时候直接从树状数组上查询前缀max即可，然后把更新出来的f[i]update进树状数组

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=100005;

int n,t[N],f[N],ans;

struct qwe

{

	int l,r;

}a[N];

bool cmp(const qwe &a,const qwe &b)

{

	return a.r<b.r;

}

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void update(int x,int v)

{

	for(int i=x;i<=n;i+=(i&(-i)))

		t[i]=max(t[i],v);

}

int ques(int x)

{

	int r=0;

	for(int i=x;i;i-=(i&(-i)))

		r=max(r,t[i]);

	return r;

}

int main()

{

	n=read();

	for(int i=1;i<=n;i++)

		a[i].l=read(),a[i].r=a[i].l+read()-1;

	sort(a+1,a+1+n,cmp);

	for(int i=1;i<=n;i++)

	{

		int l=1,r=i-1,w=0;

		while(l<=r)

		{

			int mid=(l+r)>>1;

			if(a[mid].r<a[i].l)

				l=mid+1,w=mid;

			else

				r=mid-1;

		}

		f[i]=ques(w)+1;

		update(i,f[i]);

		ans=max(ans,f[i]);

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

bzoj 1664: [Usaco2006 Open]County Fair Events 参加节日庆祝【dp+树状数组】

最新文章

热门文章