WA on #4求条
查看原帖
WA on #4求条
795344
lfxxx_楼主2025/1/12 13:52

rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int dp[N],a[N],sum[N];
int tr[N<<2];
void pushup(int p){tr[p]=max(tr[p<<1],tr[p<<1|1]);}
void update(int p,int pl,int pr,int x,int d)
{
    if(x<pl||pr<x)
        return ;
    if(pl==pr)
    {
        tr[p]=d;
        return ;
    }
    int mid=(pl+pr)>>1;
    update(p<<1,pl,mid,x,d);
    update(p<<1|1,mid+1,pr,x,d);
    pushup(p);
}
int query(int p,int pl,int pr,int L,int R)
{
    if(L<=pl&&pr<=R)
        return tr[p];
    int mid=(pl+pr)>>1;
    if(R<=mid)
        return query(p<<1,pl,mid,L,R);
    if(L>mid)
        return query(p<<1|1,mid+1,pr,L,R);
    return max(query(p<<1,pl,mid,L,R),query(p<<1|1,mid+1,pr,L,R));
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;++i)
        cin>>a[i],sum[i]=sum[i-1]+a[i];
    dp[1]=a[1];
    for(int i=2;i<=n;++i)
    {
        // for(int j=max(1,i-k);j<=i;++j)
            // dp[i]=max(dp[i],dp[j-1]+sum[i]-sum[j]);
        dp[i]=query(1,1,n,max(1LL,i-k),i-1)+sum[i];
        update(1,1,n,i,dp[i-1]-sum[i]);
    }
    cout<<dp[n];
}
2025/1/12 13:52
加载中...