自动搬运

查看原文

来自洛谷，原作者为

	Koakuma 你不能作我的诗，正如我不能做你的梦。

搬运于2025-08-24 21:39:49，当前版本为作者最后更新于2019-08-06 17:08:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

单调队列优化dp入门好题.

这里介绍3种方法(思路)

$\mathcal{Solution\ One}$

顺推.

令 $dp[i][1]$ 表示在前 $i$ 头奶牛中,选了第 $i$ 头奶牛能获得的最大效率

$dp[i][0]$ 表示在前 $i$ 头奶牛中,不选第 $i$ 头奶牛能获得的最大效率

显然可以得出以下转移方程 ( 注意 $K$ 是题目给出的区间长度)

$$dp[i][0]=max(dp[i-1][0],dp[i-1][1])$$ $$dp[i][1]=max\{dp[j][0]+\sum\limits_{j=i-K+1}^{i}E_j \} $$

可以预处理出前缀和优化掉一重循环,转移方程就变成了如下所示

$$dp[i][1]=max\{dp[j][0]+Sum[i]-Sum[j]\}$$

因为最终都要加上一个 $Sum[i]$ ,所以可以把 $Sum[i]$ 移到 $max$ 函数外,所以

$$dp[i][1]=max\{dp[j][0]-Sum[j]\}+Sum[i]\ \ \ (i-K\leq j < i) $$

这时候我们可以发现,要使 $dp[i][1]$ 最大,我们就要让 $dp[j][0]-Sum[j]$ 尽可能的大,所以只需要用一个单调队列维护长度为 $K$ 的区间中 $dp[j][0]-Sum[j]$ 的最大值就好了.

$\mathcal{Solution\ Two}$

顺推.但状态和之前描述的有些不同

令 $dp[i]$ 表示到前 $i$ 头奶牛为止能得到的最大效率

我们可以在区间 $[i-K,i]$ 间枚举休息的奶牛,所以转移方程就可以初步推出

$$dp[i]=max\{dp[j-1]+\sum\limits_{k=j+1}^{i}E_k\}\ \ \ (i-K\leq j\leq i) $$

同样,我们预处理出前缀和进行优化

$$dp[i]=max\{dp[j-1]+Sum[i]-Sum[j]\}\ \ \ (i-K\leq j\leq i) $$

然后也是把 $Sum[i]$ 移到外面

$$dp[i]=max\{dp[j-1]-Sum[j]\}+Sum[i]\ \ \ (i-K\leq j\leq i) $$

我们发现,这里又可以用一个单调队列维护 $dp[j-1]-Sum[j]$ ,问题也就迎刃而解了.

$\mathcal{Solution\ Three}$

逆推,正难则反.

重点讲逆推法

由于题目要求区间 $[1,N]$ 中不能有连续超过 $K$ 头的奶牛,也就是两头休息的奶牛间的距离是 $\leq$ $K$的 (这里的"距离"指奶牛的数量,单位 $1$ 即为一头奶牛),并且我们要求的是能获得的最大的效率,反过来想,也就是当损失的效率值越少时,能获得的效率也就越大,所以我们可以将问题转化为求出最小的效率损失.

想到这里,$dp$ 的模型就很自然而然地出来了

令 $dp[i]$ 表示前 $i$ 头奶牛且第 $i$ 头奶牛不工作时的最小损失

则状态转移方程为

$$dp[i]=min\{dp[j]\}+E[i]\ \ \ (i-K-1\leq j<i)$$

这里 $j$ 的左边界为 $i-K-1$ 而不是 $i-K$ 的原因是如果不选第 $i$ 头奶牛则上一头休息的奶牛的位置就是 $i-K-1$ ,也就是说,此时我们单调队列维护的是长度为 $K+1$ 的区间中 $dp[j]$ 的最小值.

另外,这里有个小技巧就是最后一段区间的奶牛可能全都不休息,所以我们可以加一个编号为 $N+1$ 的虚点,最终答案即为 $\sum\limits_{i=1}^{N}E_i-dp[N+1]$.

$\mathcal{After\ Writing}$

此篇文章是笔者为了加深印象而写的,讲的可能比较快,有些关于变量边界的问题还请读者自行画图理解,或者在评论区指出,笔者会尽己所能解疑的.如果文章有什么漏洞或者错误,还请你们指出,感激不尽.