WA 90 求助

Disjoint_cat @ 2022-10-02 11:28:17

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005;
ll n,k,a[N],sum[N],dp[N],p[N];
deque<ll>q;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
    q.push_back(0);
    for(int i=1;i<=n;i++)
    {
        dp[i]=sum[i]+p[q.front()];
        p[i]=dp[i]-sum[i+1];
        while(q.size()&&p[q.back()]<p[i])q.pop_back();
        q.push_back(i);
        while(q.size()&&i-q.front()>k)q.pop_front();
        //for(int j=0;j<q.size();j++)cout<<q[j]<<" ";
        //cout<<endl;
    }
    cout<<dp[n];
    return 0;
}

by 蔡竣凯 @ 2022-10-02 11:58:06

@Donotplaygame

把第16行移到for循环后面，是求完以后再更新。

第17行是 dp[i - 1] - sum[i]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1000005;
ll n,k,a[N],sum[N],dp[N],p[N];
deque<ll>q;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
    q.push_back(0);
    for(int i=1;i<=n;i++)
    {
        p[i]=dp[i - 1]-sum[i];
        while(q.size()&&p[q.back()]<=p[i])q.pop_back();
        q.push_back(i);
        while(q.size()&&i-q.front()>k)q.pop_front();
        dp[i]=sum[i]+p[q.front()];
        //for(int j=0;j<q.size();j++)cout<<q[j]<<" ";
        //cout<<endl;
    }
    cout<<dp[n];
    return 0;
}

by Disjoint_cat @ 2022-10-02 12:04:50

@蔡竣凯 谢谢大佬%%%（\color{white}\text{同校的}