stl queue全面注释版,如有疑问欢迎斧正
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int n,m;
int w[N],f[N];//选择第i个数为结尾符合题意的最小代价,最终答案从最后到n-m+1里找
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>w[i];
deque<int>q;//维护当前合法(可继承)的f[i],其中记录的是下标,因为队头出队看下标,队尾出队看f[下标],要是记录的是f[]值,从f[]无法找到对应的下标,但是通过下标可以找到f值
q.push_back(0);//先输入一个0
for(int i = 1;i<=n;i++)
{
if(q.size()&&q.front()<i-m)q.pop_front();//如果辅助队列对头(位置)超出了我们的范围,那就把它删了
f[i] = f[q.front()]+w[i];//状态转移
while(q.size()&&f[i]<=f[q.back()])q.pop_back();//如果f[i]更小(更符合要求)就一直删
q.push_back(i);//新来的数有潜力(后面数字大小未知,必须留下)必须参与队列
}
int res=1e9;
for(int i=n;i>=n-m+1;i--)res=min(res,f[i]);
cout<<res;
}
看不懂可以问问