青鸟_Blue_Bird @ 2020-11-04 08:36:56
RT, 蒟蒻从暴力
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define int long long
#define ll long long
template <class T>
inline void read(T& a){
T x = 0, s = 1;
char c = getchar();
while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
a = x * s;
return ;
}
int dp[N];
int sum[N], w[N];
int n, k;
int d[N];
deque <int> q;
int que(int x){
d[x] = dp[x - 1] - sum[x];
while(!q.empty() && d[q.back()] < d[x]) q.pop_back();
q.push_back(x);
while(!q.empty() && q.front() < x - k) q.pop_front();
return d[q.front()];
}
signed main(){
read(n), read(k);
for(int i = 1; i <= n; i++){
read(w[i]); sum[i] = sum[i - 1] + w[i];
}
for(int i = 1; i <= n; i++)
dp[i] = que(i) + sum[i];
cout << dp[n] << endl;
return 0;
}
by Dancing_Wave @ 2020-11-04 09:43:49
到抄题解珂海星
by wocaicai @ 2020-11-04 11:22:53
%%%%%%%%%膜就对了