OI动态规划&&优化 简单学习笔记

时间:2021-12-08 17:03:20

持续更新!!

DP的难点主要分为两类,一类以状态设计为难点,一类以转移的优化为难点。

DP的类型

序列DP

【例题】BZOJ2298 problem a

数位DP

常用来统计或者查找一个区间满足条件的数,然后按数位顺序DO,一般需要仔细分情况讨论,常见处理如把区间拆为\([1,l),[1,r]\),记忆化,预处理等。
【例题】BZOJ3131 淘金


概率DP

概率DP是对一类求时间概率或者期望概率DP的总称。
对于求概率问题,有时利用补集转化,有时将其转化为计数问题。求期望大多利用期望的线性性来解决问题。还有一些较难的题目会用到贝叶斯公式。
【例题】BZOJ4008 亚瑟王
【例题】codeforces 113D

\(P(x,y)=P(y|x)P(x)\neq P(y)(x)\)

\(P(y|x)P(x)=P(x|y)P(y)\)

移项得出贝叶斯公式——

\[P(y|x)=\frac{P(x|y)P(y)}{P(x)}\]


树形DP

【例题】BZOJ3611 大工程
【例题】BZOJ2734

树的直径

树的重心

树上最大权独立集

树形依赖背包

在dfs序上DP

虚树

在原树上只保留需要的点和他们的LCA的树称为虚树。


状压DP

基于状态压缩的 DP 是由于状态用单个简单的变量直接存储存在空 间的浪费, 而采用压缩的状态的动态规划, 例如: • 插头 DP: 维护当前已决策和未决策的一条 Z 字形的轮廓线的插 头状态, 用括号序列配对插头, 每次只需分情况讨论即可, 但是这 类 DP 的显著特点就是情况繁多, 使用时须细心

【例题】BZOJ3836 tourism
【例题】BZOJ2734 集合选数


DP套DP

某些DP问题的子问题不能简单地解决,而必须用另一个DP解决的问题。
即:外面的DP的状态是存的里面的DP各个状态的值,利用里层的状态来判断外层的DP是否合法,类似的问题有LCS为定值的序列的方案数等等。
【例题】BZOJ 3864


DP的优化

形式优化

【例题】BZOJ2436 嘉年华

决策单调性

【例题】诗人小G
什么是决策单调性(大家可以百度:浅析1D1D动态规划的优化)

如果导函数递增、求最大值(柠檬),或者导函数递减、求最小值,要用单调栈。

如果导函数递增、求最小值(本题),或者导函数递减、求最大值(Lightning Conductor),要用单调队列。

常见的决策单调性优化有四边形不等式优化,以及一些1D/1D动态规划的优化。

更多总结,题目联系,启发思想,参见flash_hu的博文——DP优化总结

四边形不等式优化:

以下内容摘抄自这里这里

对于如下的状态转移方程(max与min等价)
\[m(i,j)=min\{m(i,k-1),m(k,j)+w(i,j)\}(i\le k\le j)\]

区间包含的单调性

如果对于\(i\le i'\le j\le j'\),有\(w(i',j)\le w(i,j')\)

四边形不等式

如果对于\(i\le i'\le j\le j'\),有\(w(i,j)+w(i',j')\le w(i',j)+w(i,j')\),我们称函数w满足四边形不等式。

定理一

如果上述的w函数同时满足区间单调性和四边形不等式,那么函数m也满足四边形不等式性质。

定理二

设\(s(i,j)\)表示\(m(i,j)\)取得最优值时对应的下标(即\(i\le k\le j\)时,k处的w值最大,则\(s(i,j)=k\))。那么假如\(m(i,j)\)满足四边形不等式,那么\(s(i,j)\)单调,即\(s(i,j)\le s(i,j+1)\le s(i+1,j+1)\)

具体如何优化呢?我们原来在计算\(f[i][j]\)的时候,枚举的k值范围是\([i,j)\),所以单次转移的复杂度是\(O(n)\),现在,我们既然知道了\(p[i][j-1]\le p[i][j]\le p[i+1][j]\),我们只需要把k的枚举范围改成\(p[i][j-1]\)至\(p[i+1][j]\)就好了!总体复杂度就变成了O(n^2)了!注意这里是闭区间,即p[i][j-1]和\(p[i+1][j]\)都能取到。下面给出简单证明。

对于固定的区间长度len,有

\(f[i][i+len]\)的决策范围为\(p[i][i+len-1]\)至\(p[i+1][i+len]\)

\(f[i+1][i+len+1]\)的决策范围为\(p[i+1][i+len]\)至\(p[i+2][i+len+1]\)

\(f[i+2][i+len+2]\)的决策范围为\(p[i+2][i+len+1]\)至\(p[i+3][i+len+2]\)

斜率优化

凸单调性


容斥

栋栋的容斥总结

【例题】ZJOI2016 小星星

部分分+正解解题报告以及相似类型题目:参见shadowice1984

技巧们

1、凑系数【例题】BZOJ4671 异或图
2、平方处理【例题】BZOJ1566 管道取珠
3、反射法