codePanclA @ 2023-07-11 16:51:59
找不到错误了,难顶
#include <math.h>
#include <string.h>
#include <deque>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
const int N=1e7;
long long dp[N],sum[N],d[N];
deque<int> q;
long long n,k;
long long findm(int x){
d[x]=dp[x-1]-sum[x];
q.push_back(0);
while(!q.empty()&&d[x]>d[q.back()]) q.pop_back();
while(!q.empty()&&x-q.front()>k) q.pop_front();
q.push_back(x);
return d[q.front()];
}
int main(int argc, char** argv) {
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>sum[i];
sum[i]+=sum[i-1];
}
for(int i=1;i<=n;i++){
dp[i]=findm(i)+sum[i];
}
cout<<dp[n];
return 0;
}