决策单调性dp学习笔记

把标签连起来念就是标题。（模仿成爷）

这是一个很有用但不出名的算法。

网上教学很少，我需要一篇学习笔记来防止自己忘了。

这篇文章记录了决策单调性dp的两种写法以及例题。

什么是决策单调性优化

顾名思义，就是利用dp时决策的单调性优化dp。

似乎单调队列优化dpa和斜率优化dp都是决策单调性的一种，但这只是一篇关于普通决策单调性dp的学习笔记。

一些准备工作

为了方便理解，我们把dp时每个决策看成一个函数。

例如这个式子$f_i=min_{j=1}^{i-1}(f_j+w_{i,j})$，$w_{i,j}$的意义随题目内容所变化。

我们在对i作出决策的时候，将前面的j看成一个函数，即$f_i=min_{j=1}^{i-1}g_j(i),g_j(i)=f_j+w_{i,j}$

如果你发现对于任意两个函数$g_j$和$g_k$满足$j<k$且$g_k$的增长速度比$g_j$快的话，你就证明了这个dp具有决策单调性。

我们通常用写暴力打表代替这种证明

解决这种问题的方法

二分

发现每个$j$所控制的区间是递增且连续的，设决策j控制的区间是$[l_j,r_j]$，这些区间取并就是$[1,n]$，那么就可以开一个类似单调队列的东西维护这些决策区间。

1. 当一个决策$j$要进入队列时，它首先要和队尾决策比较，如果在$n$这个位置队尾决策都没有$j$优的话，显然这个决策永远都干不过$j$了，把他弹出直到队列为空或不满足条件。停止后进入2.，该让$j$进入队列了。

2. 当一个决策进入队列时，如果队列为空，这个决策控制的区间就是$[1,n]$，结束。否则进入3.。

3. 设队尾决策为$k$，说明$l_j\in[l_k+1,r_k]$，可以在这个范围里二分找到$l_j$的值，并更新$r_k$，$j$进队，$r_j=n$。结束。

那么我们完成了维护工作，更新答案就是取出队首的元素，如果当前$i$超出了队首元素的控制区间，就弹掉队首直到$i$可以被更新。

这个做法的缺陷是必须能快速比较两个函数值的大小。

例题：

[POI2011]Lightning Conductor

[NOI2009]诗人小G

分治

分治做法非常的好写和容易理解，分治每一层求解一段区间$[l,r]$的解在$[x,y]$中的情况，之后暴力求出$[l,r]$中点$mid$的解，同时你也得到了$[l,mid-1]$和$[mid+1,r]$的解的范围，那么就得到了两个规模减半的小问题。

复杂度分析的话，一共有$log\ n$层，每层加起来是$o(n)$，所以是$n\ log\ n$的。不过要注意的一点是，这个函数会被调用n次，所以如果$w_{i,j}$需要维护一个桶的话，每次清空桶复杂度是假的。这时候用莫队就非常好使，因为指针移动了$n\ log\ n$次，所以复杂度是对的。

例题：

CF868F Yet Another Minimization Problem

写在后面

其实决策单调性优化dp的重点在于找到决策单调性，知道了这个之后剩下的基本是板子，这也是我只给出三个例题的原因，当你知道有决策单调性后，这些题就基本做完一半了。

所以读者不妨自己证明下上面例题的单调性。