题解：P10381 「HOI R1」杂赛选比

· · 题解

P10381 「HOI R1」杂赛选比

思路

显然，此题为一道 DP 题。

设 dp_{i} 为从 i 至 n 的最大金币数量，得转移方程：

dp_{i}= \max(a_{i},\max_{1\le j \le a_{i} }dp_{i+j}+\sum_{k=1}^{j-1}a_{i+k} )

时间复杂度太高，为 O(n^2) ，考虑优化。

不难发现，可每次转移可转化为：

故而采用线段树优化（带懒标记 lazy_tag ），时间复杂度 O(n\log n) 。

代码

#include<bits/stdc++.h>
using namespace std;
#define lid (id<<1)
#define rid (id<<1|1)
#define int long long
int t,n,a[100005],dp[100005];
struct seg_tree{
    int l,r,val,lazy_tag;
}tr[400005];//四倍空间
void update(int id,int val)
{
    tr[id].val+=val;
    tr[id].lazy_tag+=val;
}

void pushup(int id)
{
    tr[id].val=max(tr[lid].val,tr[rid].val);
}

void pushdown(int id)
{
    if(!tr[id].lazy_tag)
        return ;
    update(lid,tr[id].lazy_tag);
    update(rid,tr[id].lazy_tag);
    tr[id].lazy_tag=0;
}

void build(int id,int l,int r)
{
    tr[id].l=l;
    tr[id].r=r;
    tr[id].lazy_tag=tr[id].val=0;
    if(l>=r)
        return ;
    int mid=(l+r)>>1;
    build(lid,l,mid);
    build(rid,mid+1,r);
}

void modify(int id,int l,int r,int val)
{
    if(l>r)
        return ;
    if(tr[id].l>=l&&tr[id].r<=r)
        return update(id,val);
    pushdown(id);
    int mid=(tr[id].l+tr[id].r)>>1;
    if(l<=mid)
        modify(lid,l,r,val);
    if(r>mid)
        modify(rid,l,r,val);
    pushup(id);
}

int query(int id,int l,int r)
{
    if(l>r)
        return 0;
    if(tr[id].l>=l&&tr[id].r<=r)
        return tr[id].val;
    pushdown(id);
    int ans=0;
    int mid=(tr[id].l+tr[id].r)>>1;
    if(l<=mid)
        ans=max(ans,query(lid,l,r));
    if(r>mid)
        ans=max(ans,query(rid,l,r));
    return ans;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);  cout.tie(0);
    cin>>t;
    for(int j=1;j<=t;j++)
    {
        cin>>n;
        build(1,1,n);
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=n;i;i--)
        {
            dp[i]=a[i];
            int l=i+1;
            int r=min(i+a[i],n);
            dp[i]=max(dp[i],query(1,l,r));
            modify(1,l,n,a[i]);
            modify(1,i,i,dp[i]);
        }
        cout<<dp[1]<<"\n";
    }
    return 0;
}

Thanks For Watching.