单调性优化DP

动态规划

作业部落链接

---

一、概述

裸的DP过不了，怎么办？
通常会想到单调性优化

• 单调队列优化
• 斜率优化
• 决策单调性

二、题目

• 洛谷 P2120 [ZJOI2007]仓库建设
• 洛谷 P2900 [USACO08MAR]土地征用
• 洛谷 P3195 [HNOI2008]玩具装箱
• 洛谷 P3628 [APIO2010]特别行动队
• 洛谷 P4360 [CEOI2004]锯木厂选址(留作复习)
• 洛谷 P4072 [SDOI2016]征途
• 洛谷 P3648 [APIO2014]序列分割
• 洛谷 P4027 [NOI2007]货币兑换
• 洛谷 P2627 修剪草坪
• 洛谷 P2569 [SCOI2010]股票交易
• 洛谷 P2254 [NOI2005]瑰丽华尔兹
• BZOJ 4709 柠檬

三、各种方法

单调队列优化

你会发现$i$这个状态是由$[i-k1,i-k2]$转移过来的，而且$j$对于$[j+k2,j+k1]$的贡献是一样的，和后一个接受贡献的$i$无关，那么就可以使用单调队列优化了，每次就是队首的点来更新后面的状态
题目：修剪草坪、股票交易

斜率优化

当发现$j$转移到$i$的时候贡献和$i$有关系的时候，那么就要用到斜率优化了
比如说

$$dp[i]=min(dp[i],dp[j]+(A[i]-A[j])^2)$$ 本来应该枚举$j$的，但是把式子化简 $$dp[j]+A[j]^2=2A[i]A[j]+(dp[i]-A[i]^2)$$
再看看 $$y=kx+b$$ 诶很像哦，那么我们要求的$dp[i]$就是截距$+A[i]^2$咯
那么一个状态$j$可以抽象成一个点$(x,y)=(A[j],dp[j]+A[j]^2)$
此时斜率是$2A[i]$，那么最小的截距就可以由上凸壳的最下端点转移而来
所以用单调队列维护凸壳就可以实现$O(1)$转移了
例题见上题单序列分割及以上所有，建议初学者先做[HNOI2008]玩具装箱

但是当斜率不是单调的而且查询区间是[l,r]的时候
就要可持久化了，用树存单调栈的情况然后倍增查询
例题见2018.5.30考试题T2(记住今天你被别人摁在地上打score1/5)

决策单调性优化

暂不会，例题见柠檬

四、做题经验

斜率优化通常维护这种东西

然后红线就是斜率，黑线就是要维护的凸壳
考虑清楚斜率的单调性以及正负就好了
一般斜率优化的题很好写暴力，多拍一下