70pts求助!!
查看原帖
70pts求助!!
1049051
JiuZhE66666楼主2024/3/9 00:01
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node
{
    ll v,x;
    bool operator <(const node &b)const {return b.v<v;}
};
ll dp[1000005]={0};
ll a[1000005];
int main()
{
    ll n,k,sum=0;
    cin>>n>>k;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }

    priority_queue<node> q;
    q.push({0,0});
    ll ans=2e18;
    for(ll i=1;i<=n;i++)
    {
        while(q.size()&&i-q.top().x>k+1) q.pop();
        dp[i]=a[i];
        if(q.size()) dp[i]+=q.top().v;
        if(i>1)q.push({dp[i-1],i-1});
        if(i+k>=n)ans=min(ans,dp[i]);
        //cout<<dp[i]<<endl;
    }

    cout<<sum-ans;
    return 0;
}

2024/3/9 00:01
加载中...