题解 P2627 【修剪草坪】

· · 题解

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

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

\mathcal{Solution\ One}

顺推.

令 dp[i][1] 表示在前 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}

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