自动搬运

查看原文

来自洛谷，原作者为

	729hao 3^6

搬运于2025-08-24 23:01:48，当前版本为作者最后更新于2024-11-27 13:32:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

思路

令 $dp_i$ 表示选取 $i$ 作为最右边的花的可取的最大数量。

显然，$i$ 只能从满足 $j<i-l_i\land i>j+r_j$ 的 $j$ 转移过来。即对于每一个 $i$，我们要找到 $1$ 到 $i-l_i-1$ 中，$j+r_j<i$ 的最大值。

显然可以主席树优化。

具体地，主席树节点范围为 $L$ 到 $R$ 维护对于所有 $L<j+r_j<R$ 的 $j$ 中 $dp_j$ 的最大值。求出 $dp_i$ 后再更新第 $i$ 棵树。

AC Code

#include<bits/stdc++.h>
using namespace std;
namespace cs{
	#define LL long long
	const int N=2e5;
	int n,l[N+5],r[N+5],dp[N+5];
	int sgcnt,root[N+5];
	struct Segment{
		int ls,rs;
		int ma;
	}Tree[25*N+5];
	void Build(int& id,int L,int R){
		id=++sgcnt;
		if(L==R)return;
		int mid=L+R>>1;
		Build(Tree[id].ls,L,mid);
		Build(Tree[id].rs,mid+1,R);
	}
	int Query(int id,int l,int r,int L,int R){
		if(l>R||r<L)return 0;
		if(l>=L&&r<=R)return Tree[id].ma;
		int mid=l+r>>1;
		return max(Query(Tree[id].ls,l,mid,L,R),Query(Tree[id].rs,mid+1,r,L,R));
	}
	void Pushup(int id){
		Tree[id].ma=max(Tree[Tree[id].ls].ma,Tree[Tree[id].rs].ma);
	}
	void Modify(int& id,int ori,int l,int r,int x,int val){
		id=++sgcnt;
		Tree[id]=Tree[ori];
		if(l==r){
			Tree[id].ma=max(Tree[id].ma,val);
			return;
		}
		int mid=l+r>>1;
		if(x<=mid)Modify(Tree[id].ls,Tree[ori].ls,l,mid,x,val);
		else Modify(Tree[id].rs,Tree[ori].rs,mid+1,r,x,val);
		Pushup(id);
	}
	int main(){
		ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//		freopen("bouquet.in","r",stdin);
//		freopen("bouquet.out","w",stdout);
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>l[i]>>r[i];
			l[i]=max(i-l[i],1);
			r[i]=min(i+r[i],n);
		}
		Build(root[0],1,n);
		for(int i=1;i<=n;i++){
			dp[i]=Query(root[l[i]-1],1,n,1,i-1)+1;
			Modify(root[i],root[i-1],1,n,r[i],dp[i]);
		}
		cout<<Tree[root[n]].ma;
		return 0;
	}
}
int main(){
	cs::main();
	return 0;
}