Lee • 1天前
using namespace std; deque<pair<int, int>>qmin; long long dp[100001]; int main() {
int n,k;
long long sum=0;
cin>>n>>k;
qmin.push_back({0,0});
for(int i=1;i<=n;i++){
int val;
cin>>val;
sum+=val;
if(!qmin.empty()&&qmin.front().second+k<i){
qmin.pop_front();
}
dp[i]=dp[i-1];
while(!qmin.empty()&&qmin.back().first>=dp[i]){
qmin.pop_back();
}
qmin.push_back({sum-dp[i],i});
dp[i]=min(dp[i],sum-qmin.front().first);
}
cout<<dp[n];
return 0;
}
评论:
请先登录,才能进行评论