[关闭]
@xzyxzy 2018-05-30T14:09:30.000000Z 字数 897 阅读 735

单调性优化DP

动态规划

作业部落链接


一、概述

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

二、题目

三、各种方法

单调队列优化

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

斜率优化

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

本来应该枚举的,但是把式子化简

再看看
诶很像哦,那么我们要求的就是截距
那么一个状态可以抽象成一个点
此时斜率是,那么最小的截距就可以由上凸壳的最下端点转移而来
所以用单调队列维护凸壳就可以实现转移了
例题见上题单序列分割及以上所有,建议初学者先做[HNOI2008]玩具装箱

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

决策单调性优化

暂不会,例题见柠檬

四、做题经验

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注