E43【模板】单调队列优化DP 烽火传递

// 单调队列+DP O(n)
#include<bits/stdc++.h>
using namespace std;

const int N=200010;
int n,m,a[N];
int q[N],f[N];

int main(){
  cin>>n>>m;
  for(int i=1; i<=n; i++) cin>>a[i];
  
  int ans=2e9;
  for(int i=1,h=1,t=0; i<=n; i++){
    while(h<=t && q[h]<i-m) h++;
    while(h<=t && f[q[t]]>=f[i-1]) t--;
    q[++t]=i-1;
    f[i]=f[q[h]]+a[i];
    if(i>=n-m+1) ans=min(ans,f[i]);
  }
  cout<<ans;
}

#include<bits/stdc++.h>//by scy
using namespace std;
const int N=1110000;
int a[N],f[N],q[N];
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    
    int l=1,r=1; q[1]=0;
    for(int i=1;i<=n;i++)
    {
		while(l<=r && i-q[l] > m   ) l++;
        f[i]=f[q[l]]+a[i];
		
		while(l<=r && f[q[r]]>=f[i] ) r--;
		q[++r]=i;
    }
    
    int ans=(1<<30);
    for(int i=n-m+1;i<=n;i++)ans=min(ans,f[i]);
    printf("%d\n",ans);
    
    return 0;
}