题解：P10845 [EGOI2024] Bouquet / 花束制作

729hao · 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;
}