动态规划（算法竞赛、蓝桥杯）--单调队列优化烽火传递

1、B站视频链接：E43【模板】单调队列优化DP 烽火传递_哔哩哔哩_bilibili

题目链接：https://loj.ac/p/10180

#include <bits/stdc++.h> 
using namespace std;
const int N=2e5+10;
int n,m,w[N],f[N],q[N];

int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>w[i];
  
  int ans=2e9;
  int h=1,t=0;                          //清空队列
  for(int i=1;i<=n;i++){                //枚举序列
    while(h<=t && f[q[t]]>=f[i-1]) t--; //队尾出队(队列不空且新元素更优)
    q[++t]=i-1;                         //队尾入队(存储下标 方便判断队头出队)
    if(q[h]<i-m) h++;                   //队头出队(队头元素滑出窗口)
    f[i]=f[q[h]]+w[i];                  //转移
    if(i>n-m)ans=min(ans,f[i]);//只在最后的区间更新答案 
  }
  cout<<ans;
}

#include <bits/stdc++.h> 
using namespace std;
const int N=2e5+10;
int n,m,w[N],f[N],q[N];

int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>w[i];
  
  int ans=2e9;
  int h=1,t=0;
  deque<int> q;//用队列存下标                         
  for(int i=1;i<=n;i++){//枚举序列
    while(q.size()&&f[q.back()]>=f[i-1])q.pop_back();
    q.push_back(i-1);
    if(q.front()<i-m)q.pop_front();
    f[i]=f[q.front()]+w[i];
    if(i>n-m)ans=min(ans,f[i]);//只在最后的区间更新答案 
  }
  cout<<ans;
}