DP专题

 作为一种十分常见的题目类型，dp经常出现在noip以及更高的赛场上，所以这里就总结一下常见的dp类型和优化方法 ## 1.背包 背包作为一种最常见的dp类型，经常会和其他形式的题目结合起来，那么对于各种的背包，首要要能看出模型和类型 关于背包的类型，背包九讲很详细的总结了 然而关于建立模型最主要的是要点则是在分析对于各种参数在向后继承时的有无后效性，与此同时，参数的大小范围也很重要 在某些时候对于会卡空间的dp要选择滚动数组的方式来减小空间的利用 ## 2.区间dp 区间dp，那么就是一种明显的在某一个线性的集合当中，求某一种值，而在这里通常是可以将一个大区间分化为两个小区间在合起来 可以将这个行为看成分割的地方是在该区间里的最后一次的运算点，以此得出最优解 当然，对于区间dp来说，一般会和环形的数据共同出现，这时就需要化环为链，然后在进行区间dp 普通的区间dp的时间复杂度一般为O($n^{3}$) 对于区间dp来说，有一种常见的优化方式就是平行四边形优化 当然，该优化的适用范围较小，只有在dp明显有单调性的时候才能使用，也就是说，当区间i到j的断点一定在区间i+1到j的断点的左边以及一定在i到j-1的右边的时候才能使用，即用这种方式优化枚举断点的范围，然后就能将时间复杂度从O($n^{3}$)优化到O($n^{2}$) ## 3.树形dp 树形dp是基于树形的图（或者不是树形的图）而进行的一种dp 该dp通常可以根据有无方向分成两种解法 ### (1).有方向的树 第一种就是有方向dp，可以从根向叶子直接进行dp或反过来 有方向的dp一般有两个特点，一是树上的边是单向边，二是有一个固定根，凡是满足这两个条件之一的图上的dp一般就是树形的dp 对于树形的dp，一般是在大法师的基础上对方程函数进行修改，然后在向下搜索之前或者回归之后对当前点的数据进行更新 如果以这为定义的话，其实类似于求子树的节点总数一样 ### (2).无方向的树 第二种就是无方向的dp，可以认为是边无方向或根不确定等情况 对于这种dp，我们就是先进行一次大法师，从上向下dp一遍，得到除了向上的路径以外都算出来，然后再进行一次大法师，将从根过来的路径和数据转移过来 注意，一般这时的dp要把从自己这里到根的部分减去再转移到自己这里 ## 4.概率dp 很多时候，概率dp是有后效性的，这时候就可以通过多次dp或者解方程的方式来得到dp 一般的时候概率dp和背包很想，只要多想想就可以做出来的 ## 5.状压dp 对于许多的时候，可能某一个状态十分的复杂，比如说很多的1和0，这时候就需要状压 状压一般采用二进制压位或者k进制压位，这时的状态转移一般也是使用位运算的取或、取与和位移三种方式来进行状态的改变 对于这一点练多了就好很多，除此之外，就需要对于压位的检验的debug的函数的编写 ## 6.最值优化 很多时候O($n^{2}$)的算法是会超时的，而这时，我们的很多时候的决策的前一个点对和该点的大小是没有关系的，这个时候可以将所有需要转移的状态放入max或min数组里 每当我们新得到一个点的状态时就可以将状态与数组中的状态比对然后更新 ## 7.单调队列优化 在很多时候，dp是存在限制的，例如说只能在前k个状态转移过来，这个时候可以采用单调队列就可以了，在队头的是最优解，然后在之后每次进来一个点都从对尾出向外弹出比当前点更差的点，然后每当队头的元素不能再用的时候就将其弹出。 当然，要能保证前面更优的解对后面来说也更优 ## 8.优先队列优化 当我们的dp题目需要一定的最优解是可以用优先队列维护并取最优值 这个时候要注意是要用优先队列还是用单调队列 ## 9.斜率优化 有时候我们发现$O(n^2)$的dp会超时，但是有没有办法用前面的三种优化来解决这个问题，即当前点的dp与前面的点并没有完全的分离，而是有一定的乘积，这个时候，我们就要改变优化的方式，采用斜率优化 这是，我们对于每一个点，都将其与后面dp的时候的点有关的部分作为x，与其无关的部分作为y，然后将这些所有的点都放到一个平面坐标系上，而在一般的情况会发现 $dp[i]=dp[j]+a[i]*b[j]+c[i]$ 将其转写成 $b=y+k*x+b_0$ 将y加上x乘上k得到的值写成等式，就会发现其实是这条直线的y轴上的截距，那么我们将所有的斜率k放到平面上看，就会发现，所有的最优解都在一个凸包上，所以我们的斜率优化就是维护一个凸包，然后就可以将问题优化至$O(n)$ 在很多时候斜率都是递减或递增的，在这种时候，一般在队头的点没有队列里第二个点更优时就可以弹出了。 ### *补充 注意，斜率优化的前提是在保证斜率都是单调的情况下进行。 当然，如果是在斜率不单调的时候就不能将对头的点弹出，而是要在凸包上二分找到最优点 同时，注意决策的单调性，就是说，下一个点的x或者y至少有一个是单调的才能用斜率优化，否则需要进行插入和删除，会很麻烦，使复杂度降低