主播主播，你的单调队列优化还是太吃脑子了，有没有不吃脑子又吃码力的方法呢

有的兄弟有的

我们已经知道了对于每一个 $dp_i$ 有：

那我们可以直接使用线段树优化，不吃脑子但是吃码力

#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
bool Test_MLE_start;
const int N=2*1e5+10;
int T=1,n,m,ans=2e9;
int a[N],dp[N];
struct tree{
	int l,r,data;
}t[N<<2];
inline int reads(){
	char c=getchar();
	int sum=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		sum=(sum<<3)+(sum<<1)+(c^'0');
		c=getchar();
	}
	return sum*f;
}
inline void files(){
	freopen("A.in","r",stdin);
//	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
void pushup(int p){
	int x=p<<1,y=p<<1|1;
	t[p].data=min(t[x].data,t[y].data);
}
void builds(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r) return;
	int mid=(l+r)>>1;
	int x=p<<1,y=p<<1|1;
	builds(x,l,mid),builds(y,mid+1,r);
	pushup(p);
}
void changes(int p,int l,int r,int d){
	if(l<=t[p].l&&t[p].r<=r){
		t[p].data=d;
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	int x=p<<1,y=p<<1|1;
	if(l<=mid) changes(x,l,r,d);
	if(r>mid) changes(y,l,r,d);
	pushup(p);
}
int asks(int p,int l,int r){
	if(l<=t[p].l&&t[p].r<=r) return t[p].data;
	int mid=(t[p].l+t[p].r)>>1;
	int x=p<<1,y=p<<1|1;
	int ans=2e9;
	if(l<=mid) ans=min(ans,asks(x,l,r));
	if(r>mid) ans=min(ans,asks(y,l,r));
	pushup(p);
	return ans;
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	T=reads();
	while(T--){
		clr();
		n=reads(),m=reads();
		for(int i=1;i<=n;i++) a[i]=reads();
		builds(1,0,n);
		for(int i=1;i<=n;i++){
			int x=asks(1,max(0ll,i-m),i-1);
			dp[i]=x+a[i];
			changes(1,i,i,dp[i]);
		}
		for(int i=n-m+1;i<=n;i++) ans=min(ans,dp[i]);
		printf("%lld\n",ans);
	}
	return 0;
}

设 f[i] 表示前 i 头牛，球到达牛 i 手中，最小的总代价

则最后一次传球，球可能到达 n-m+1, n-m+2, ……, n 的手中

所以 ans = min( f[n-m+1], f[n-m+2], ……, f[n]

对于任意 i

f[i]=min(f[i],f[j]+a[i])

故

for(int i=1;i<=n;i++)
{
  for(int j=max(0,i-m);j<i;j++)
  {
    f[i]=min(f[i],f[j]+a[i]);
  }
}

复杂度 O(n^2)

类似于滑动窗口，单调队列优化