自动搬运

查看原文

来自洛谷，原作者为

	FCBM71 AFO

搬运于2025-08-24 22:16:48，当前版本为作者最后更新于2020-02-01 22:17:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

单调队列优化DP的板子题吖，很适合萌新上手

$20$ 分做法

假设 $f[i]$ 表示杀老师解决完第 $i$ 个学生累计花费的最小精力。显然对于 $i=1$ 有 $f[1]=a[1]$。

对于其他的 $i$ 号学生，我们假设杀老师是从第 $j$ 号学生直接跳过来的，那么状态转移方程分为三项： $f[j]$ 表示从之前的累计值，$(i-j-1)\times d+k$ 是应对学生调侃和移动花费的精力，$a[i]$ 是解决当前学生问题花费的精力。

当然 $j$ 是有范围的，$i-x\leq j<i$。当 $j=i-1$ 时，实际情况就是杀老师没有跳过任何学生，是解决了上一个学生问题直接移动过来的的。

对于每个 $f[i]$，只需要寻找最小的一个 $j$ 使得 $f[j]+(i-j-1)\times d$ 有最小值即可。最后输出 $f[n]$ 即可。时间复杂度 $O(n^2)$。

$100$ 分做法

只需要做一点点改动就可以拿到满分了（巨大的跨越）。

由状态转移方程知，可以影响 $f[i]$ 大小的只有 $f[j]$ 和他们的距离 $(i-j-1)$，因为 $k+a[i]$ 是个定值。

对于一个学生 $i$，假设最优策略是从 $j$ 号跳转到 $i$ 号，再任取一个不是最优的学生 $t$。那么对于学生 $i+1$，从 $j$ 跳转过来更优还是从 $t$ 跳转过来更优呢？答案一定是 $j$。因为从 $i$ 号位置改跳到 $i+1$ 位置只需要多花精力 $d$，二者都如此。原来 $j$ 更优，现在依然更优。

这意味着，我们对于每个 $f]i]$ 向前寻找最优的 $j$ 时，不需要遍历整个 $[i-x,i-1]$，只需要取出我们之前记录的最优的 $j$。这里的所有 $j$ 就可以用一个单调队列来维护。

每次得到 $f[i]$ 的流程就应该是

1.弹出单调队列的过期元素（$j<i-x$）
2.取出单调队列的第一个元素，得到 $f[i]$
3.将 $(f[i],i)$ 打包放入单调队列中，并弹出

弹出的条件是什么呢？并不是简单的 $f[j]\geq f[i]$ 才弹出。根据我们之前推出的性质，从 $j$ 跳转到某一个点 $x$，和从 $i$ 跳转到某一个点 $x$，从 $j$ 跳转一定会多花一个定值，即 $(i-j)\times d$ （注意这里一定不要-1）。所以弹出的条件就是 $f[j]\geq f[i]+(i-j)\times d$

附上核心代码，仅供参考

	deque<pair<LL,int> >q; //不开LL见祖宗
    
	if(x==1){     //杀老师不能跳过时，需特判
		for(int i=1;i<=n;++i)f[n]+=a[i];
		cout<<f[n]+k*(LL)(n-1);
		return 0;
	}
	f[1]=a[1];
	q.push_back(make_pair(f[1],1));  //预处理
	for(int i=2;i<=n;++i){
		while(!q.empty()){
			if(q.front().second<i-x)q.pop_front();
			 else break;    //弹出过期元素
		}
		LL fx=q.front().first;int lx=q.front().second;
		f[i]=fx+k+d*(LL)(i-lx-1)+a[i];  //得到f[i]
		while(!q.empty()){
			LL fx=q.back().first;int lx=q.back().second;
			if(fx+d*(LL)(i-lx)>=f[i])q.pop_back();
			 else break;   //弹出
		}
		q.push_back(make_pair(f[i],i));  //压入当前元素
	}
	cout<<f[n];