决策单调性
MCAdam
·
·
个人记录
理解
首先这里的决策单调性是广义上的决策单调性：即前后决策之间存在某些可以利用的关系
后面的内容大多数针对于这样的DP式子：\displaystyle f(i)=\max/\min \{g(j)+w(j,i)\}
还包括：按层转移的、按区间从小到大转移的高维DP
令\displaystyle p(i)\text{表示i的最优决策点},[l(i),r(i)]\text{表示i的决策区间}
如果p(i)在i\in [1,n ]上单调不减，那么这个方程就满足狭义上的决策单调性
对于一般的斜率优化，大都满足决策单调性，可以使用一般的方法来做，但因为其本身的特殊性，可以更优
转移代价只和转移位置有关
即w(j,i)只和j有关，那么i决策区间内的信息在之前已经被保留下来，就可以直接拿来使用了
更加具体的：对[l(i),r(i)]分类讨论（前提是转移区间连续）
只需要记录一个“前缀”信息就能够转移了，用一个变量就足够了
用单调队列维护，当队头信息超过当前决策区间，直接踢掉；显然对于后面入队的，且权值更佳的，前面入队且权值更劣的肯定就没有用了，直接出队就行了
每次取对头就是最优决策点，时间复杂度O(n)
非常经典的一个应用：单调队列优化多重背包
暴力DP：\displaystyle f[j]=\max\{f[j-k\times w_i]+k\times v_i\}，其中\displaystyle k\in [0,\min(m_i,\frac{j}{w_i})]
把j按照模w_i意义下分组，即j=t\times w_i+d，那么方程就变成了：
\displaystyle f[j]=\max\{f[(t-k)\times w_i+d]+k\times v_i\}
\displaystyle =\max\{f[(t-k)\times w_i+d]-(t-k)\times v_i\}+t\times v[i]
那么对于每一组有用的状态就只有\displaystyle \frac{W-d}{w_i}，总的状态就只有O(W)了
设g[k]=f[kw_i+d]-kv_i，那么转移就变为：\displaystyle g[t]=\max\{g[t-k]\}+t\times v[i]
因为有限制\displaystyle k\in [0,\min(m_i,\frac{W}{w_i})]，所以单调队列优化一下就好了（可以把k下界改为1，因为自己从自己转移没有意义）代码
这个时候就没有办法用单调队列优化，因为前面不在决策区间内的，后面的反而有可能在决策区间内，就不能直接踢掉
考虑用数据结构存储每个位置的信息，然后每一次的决策就相当于区间查找最值
P3572 [POI2014]PTA-Little Bird
暴力DP很容易列出来：\displaystyle f[i]=\min_{j=i-k}^{i-1}\{f_j+[d_i\geq d_j]\}
观察后面那一坨东西，貌似还和i有关耶，还能够单调队列吗？
注意到[d_i\geq d_j]最多只会有1的贡献，也就是如果f不相同时，即使加上这个其相对大小仍然不会有变化
也就是[d_i\geq d_j]只有在f相同时才能起到作用，所以每次入队时判断一下，首先按照f比较，f相同时再比较d就可以了
斜率优化
显然直线要比各种乱七八糟的函数要美丽多了，只需要通过各种手段去维护直线就好了
## 一道例题 [代码](https://www.luogu.com.cn/paste/lknpsja8)
[P2365 任务安排](https://www.luogu.com.cn/problem/P2365)
第一种数据：$1\leq n\leq 3\times 10^5\quad1\leq s,t_i,c_i\leq 512
第二种数据：1\leq n\leq 3\times 10^5\quad0\leq s,c_i\leq 512\quad-512\leq t_i\leq 512
第三种数据：1\leq n\leq 3\times 10^5\quad0\leq s,t_i\leq 512\quad-512\leq c_i\leq 512
第四种数据：1\leq n\leq 3\times10^5\quad0\leq s\leq 512\quad-512\leq t_i,c_i\leq 512
首先考虑暴力：
令st[i]表示t_i的前缀和，sc[i]表示c_i的前缀和，f[t][i]表示前t批包含了前i个任务的最小费用
f[t][i]=\min\limits_{j=0}^{i-1}\{f[t-1][j]+(st[i]+t\times s)\times (sc[i]-sc[j])+s\}
这是O(n^3)的暴力，想办法把它优化到O(n^2)
注意到f[t-1][j]就是从上一次直接继承过来的，我们要枚举t唯一的原因就是要加上t\times s
如果不枚举t，我们就不能得到前面开了多少次机，但我们能够知道当前这一次开机会对当前以及后面的批次都产生影响。即上一批任务最后一个j，当前开机能够造成的影响就是s\times (sc[n]-sc[j])
所以，修改f的定义，f[i]表示前i个任务分成若干批并提前计算后面影响的最小代价，那么转移为
f[i]=\min\limits_{j=0}^{i-1}\{f[j]+st[i]\times (sc[i]-sc[j])+s(sc[n]-sc[j])\}
x,k单调：单调队列（栈）+指针 代码
我们把和j没关的全部拎出来，得到：
f[i]=\min\limits_{j=0}^{i-1}\{f[j]-st[i]\times sc[j]-s\times sc[j]\}+st[i]\times sc[i]+s\times sc[n]
后面那一坨就不用考虑了，移一下项得到：
f[j]-s\times sc[j]=st[i]\times sc[j]+f[i]
这就可以看成一条斜率为st[i]的直线从下往上切到的第一个(sc[j],f[j]-s*sc[j])就是最优决策点
我们把它写成y=kx+b。其中(x,y)就表示前面的决策点，k表示要用来切的直线，b就是我们要最小（大）化的截距f[i]
因为t_i,c_i都是正数，所以k,x都是单调的
当k,x单调时，每次新加入一条直线，就可以排除掉一些无用的决策，插入新的直线也是在两端插入，用单调队列或者单调栈来维护斜率，直接移指针
在这一题中，因为k,x都是单调递增的，所以排除就决策是在头部发生，插入新直线是在队尾发生，维护一个单调队列就行了
更细致的：可以对比P5504 [JSOI2011]柠檬
$k$递增且求的是$\min$，或者$k$递减求的是$\max$，用单调队列；$k$递增且求的是$\max$，或者$k$递减求的是$\min$，用单调栈
x单调，k不单调：单调队列（栈）+二分 代码
此时t_i存在负数，那么st就不一定是递增的了，即k不存在单调性。那么就不能像前面一样（以这题为例），每次寻找最有决策点时就把队头那些斜率小的扔掉，前面那些斜率小的后面有可能成为最优决策。
没有删掉这一操作，我们只用进队（只进不出，叫队列或者叫栈都一样）来维护凸壳。寻找最优决策点的时候，就二分。
x不单调，k单调/不单调：CDQ分治/平衡树/李超线段树 代码
直接CDQ分治，先递归左边，每一层按照x排序
那么左边递归完后x就是有序的，那么就可以直接单调队列/单调栈维护凸包
那么右边就可以决策了，如果k原本就是单调的，直接在队列/栈上移指针就好了；如果k不单调，可以在凸壳上二分；如果为了避免二分，可以在决策之前对右边按照斜率排序（记得还原）
这样的时间复杂度就是O(n\log^2n)
有两种解决办法：因为斜率不会受到其他因素干扰（如果会就要再套一层CDQ），那么可以一开始做一次归并排序，把每一层的按照斜率排序的数组存下来，那就可以直接调用了（尽管这样写起来非常麻烦）
另一种非常巧妙的，在CDQ之前就可以按照斜率排序，在每层CDQ时，按照编号分配到左右两半，然后每一层按照x排序
这样子写就能够保证，递归完左半部分后，左边的编号肯定小于右边的编号，左边的x递增，右边的斜率递增/减，这样就可以直接维护了
比较有技巧的维护凸包：P2305 [NOI2014]购票
一般决策单调性
决策单调性的核心：发现决策之间的递变规律
所以会先介绍一些通用的判断决策单调性的方法，然后再介绍各种维护决策单调性的手段
判断方法
设w(x,y)是定义在整数集合上的二元函数。若对于定义域上的任意整数a,b,c,d，其中a\leq b\leq c\leq d，都有w(a,d)+w(b,c)\geq w(a,c)+w(b,c)（包含大于等于相交），则称w满足四边形不等式
定理0： 证明
若对于定义域上的任意整数a,b，其中a<b，都有w(a,b+1)+w(a+1,b)\geq w(a,b)+w(a+1,b+1)，则w满足四边形不等式
一维DP
定理1： 证明
若w函数满足四边形不等式，则f具有决策单调性
证明四边形不等式也有很多种方法：硬上各种不等式、求导、画图、打表等等
P1912 [NOI2009]诗人小G
但再大多数情况下，一维DP的决策单调性都会比较明显，如果直接观察函数看不出来，不妨直接把决策点输出来观察
区间DP
对于一般的二维DP或者更加高维的DP，其决策单调性可能只是针对于某一维度，然后通过各种方法去维护。但对于特殊的区间DP模型，有二维的四边形不等式
方程式：\displaystyle f(i,j)=\displaystyle \min_{k=i}^{j-1}\{f(i,k)+f(k+1,j)+w(i,j)\}
定理2：证明
如果w满足四边形不等式，且对于任意a\leq b\leq c\leq d，有w(a,d)\geq w(b,c)（区间包含单调性），那么f也满足四边形不等式
定理3：证明
如果f满足四边形不等式，那么对于任意i<j，有p(i,j-1)\leq p(i,j)\leq p(i+1,j)
根据这个，因为区间DP都是从小区间到大区间更新，寻找(i,j)的最优决策点只需要从[p(i,j-1),p(i+1,j)]中找就好了
可以证明这样的时间复杂度为O(n^2)
手段1：单调队列/单调栈+二分
这种方法一般是用来解决一维DP
当f有决策单调性时，\displaystyle f_i=\min_{j=0}^{i-1}{f_j+w(j,i)}可以O(n\log_2n)计算
考虑如何维护p_i，在枚举i的任意时刻，设p数组此时为：
j_1\quad j_1\quad j_2\quad j_3\quad j_3\quad j_3\quad j_4\quad j_4\quad(j_1<j_2<j_3<j_4)
当求出f_i要考虑i可以作为哪些f_{i'}(i'>i)的最优决策。根据决策单调性，会存在一个位置，使得p数组目前存储的决策，在这个位置之前都比i好，在这个位置之后都比i差
分析一下这段话：当f_i从p_i取得最优决策时，对于j,k(k>j>i)在未考虑i这个决策的时候，p_j\in \lbrack p_i,i),p_k\in \lbrack p_j,i)。讨论i这个决策对j,k的影响
1、p_j比i更优
此时p_j\in \lbrack p_i,i)，k对于j的最优决策的讨论就类似为j对于i的最优决策，故注重讨论第二种情况
2、i比p_j更优
此时p_j=i，那么对于k(k>j)，根据决策单调性可知，p_k\geq p_j=i，即j与j后面原本的最优决策都比i差，要用i替换掉它们。也就是上面所说的：会存在一个位置，使得p数组目前存储的决策，在这个位置之前都比i好，在这个位置之后都比i差
那么p数组大概就变成下面这个样子
j_1\quad j_1\quad j_2\quad j_3\quad j_3\quad i\quad i\quad i\quad (j_1<j_2<j_3<i)
那现在就是要考虑如何维护p数组，注意到p数组中经常会有一段都是相同的。建立一个队列代替p数组，队列中保存着若干个三元组(j,l,r)，表示目前p_l到p_r的值的值都是j
一开始的p数组可以表示为：
(j_1,1,2),(j_2,3,3),(j_3,4,6),(j_4,7,8)
那么i要替换掉的是整个(j_4,7,8)还有(j_3,4,6)最后那一部分。那么直接把(j_4,7,8)整个删掉，然后在(j_3,4,6)中二分出第一个决策不如i的，把它后面的都删掉，即把(j_3,4,6)变为(j_3,4,5)，然后在队尾插入：(i,6,8)
注意到队列中没有必要保存p_1到p_{i-1}的部分，直接删掉即可，删完之后，队头就是p_i，直接取出来计算f_i就行啦！
总的来说，对于每一个i\in[1,n]，有：
1、检查队头：设队头为(j_0,l_0,r_0)，若r_0=i-1，删除队头，否则令l_0=i
2、取队头保存的j为最优决策，计算出f_i
3、插入新的决策i
(\textrm{I})$取出队尾$(j_t,l_t,r_t)
(\textrm{II})$若对于$f_{l_t}$来说，$i$是比$j_t$更优的决策，即$f_i+w(i,l_t)\leq f(j_t)+w(j_t,l_t)$，记$pos=l_t$，返回$(\textrm{I})
(\textrm{III})$若对于$f_{r_t}$来说，$j_t$是比$i$更优的决策，即$f_{j_t}+w(j_t,r_t)\leq f_i+w(i,r_t)$，去往$(\textrm{V})
(\textrm{IV})$在$[l_t,r_t]$上二分，求出位置$pos$，在此之前决策$j_t$更优，在此之后$i$更优，去往$(\textrm{V})
```cpp
que[1]=(node){0,1,n};
int head=1,tail=1;
for(int i=1;i<=n;i++)
{
while(head<=tail&&que[head].r<i) head++;
que[head].l=i;//排除过时决策
f[i]=cal(que[head].p,i);//计算出f[i]
while(head<=tail&&cal(i,que[tail].l)<=cal(que[tail].p,que[tail].l)) tail--;//整块不如i的直接删掉
int low=que[tail].l,high=que[tail].r+1;
while(low+1<high)
{
int mid=(low+high)/2;
if(cal(i,mid)<=cal(que[tail].p,mid)) high=mid;
else low=mid;
}//二分出最后一块中第一个不如i的位置
que[tail].r=high-1;//更改最后一块的右端
if(high<=n) que[++tail]=(node){i,high,n};//插入新决策，注意有可能i不会为最有决策，注意判断
}
```
## 手段2：分治法
这种方法其实是用来解决一维DP的，所以也可以直接替换掉上面那种二分单调队列的做法，但可以用来解决按层转移的二维DP
直接以一道题为例子更容易理解
[CF321E Ciel and Gondolas](https://www.luogu.com.cn/problem/CF321E)
很容易想到暴力的DP，设$f[t][i]$表示前$i$个人分成$t$段的最小代价
$\displaystyle f[t][i]=\min_{j=0}^{i-1}\{f[t-1][j]+w(j,i)\}$，复杂度$O(kn^2)
其中w(j,i)=s[i][i]-2s[i][j]+s[j][j]
因为f每一层只会从上一层转移，只要证明w满足四边形不等式，那么同一层f就具有决策单调性
即证w(j,i+1)+w(j+1,i)\geq w(j,i)+w(j+1,i+1)
直接展开后，即要证明：\displaystyle s[i+1][j]+s[i][j+1]\leq s[i][j]+s[i+1][j+1]
移项：\displaystyle s[i+1][j]-s[i][j]\leq s[i+1][j+1]-s[i][j+1]
上面这个不等式显然成立，所以f在同一层中具有决策单调性
设当前要计算层数的区间为[l,r]，其决策区间为[pl,pr]
首先计算\displaystyle p(mid=\frac{l+r}{2})，那么根据决策单调性，[l,mid-1]的决策点会等于p(mid)，[mid+1,r]的决策点会大于等于p(mid)
那么就递归计算solve(l,mid-1,pl,p(mid)),solve(mid+1,r,p(mid),pr)
因为只会递归O(\log n)层，每层的[pl,pr]拼起来刚好是n，所以复杂度O(n\log n)，最后总的时间复杂度就是O(k\times n\log n)
inline void solve(int l,int r,int pl,int pr)
{
int mid=(l+r)/2,pos;
f[mid]=cal(pos=pl,mid);
for(int i=pl+1;i<=min(pr,mid-1);i++)
if(cal(i,mid)<f[mid]) f[mid]=cal(pos=i,mid);
if(l<mid) solve(l,mid-1,pl,pos);
if(r>mid) solve(mid+1,r,pos,pr);
}
手段3：分治法+类莫队
CF833B The Bakery
方程式还是和上面一样，但是w(j,i)变成统计颜色个数，无法快速求出，直接暴力就变成了O(k\times n^3)
不妨先证明其满足四边形不等式，因为是取\max所以不等式反向
\displaystyle w(j,i+1)+w(j+1,i)\leq w(j,i)+w(j+1,i+1)
即\displaystyle w(j,i+1)-w(j,i)\leq w(j+1,i+1)-w(j+1,i)
-
v[i+1]$在$[j+1,i]$中出现过：左右两边都为$0
-
v[i+1]=v[j]$并且不在$[j+1,i]$中出现过，那么左边为$0$，右边为$1
-
v[i+1]$在$[j,i]$都没有出现过，左右两边都为$1
所以w满足四边形不等式，f满足决策单调性，同样用分治法来解决
普通的分治时，为了找到mid的最优决策点，从左到右枚举决策点，然后计算w(i,mid)，计算的这个区间规模不断缩小
现在要数的是颜色，不妨模仿莫队那样，维护两个指针一直跳。不妨假设一开始两个指针的位置就在pl，那么计算mid，右端点都是固定的，左端点不断往移动，所以复杂度仍然是O(\text{决策区间长度})
那么递归到左右两边，要把指针移动到pl和p(mid)，复杂度仍然是O(\text{决策区间长度})
所以复杂度还是O(n\log n)
inline int cal(int j,int i)
{
while(tail<i) ins(++tail);
while(head>j+1) ins(--head);
while(tail>i) del(tail--);
while(head<j+1) del(head++);
return g[j]+ans;
}
手段4：凸优化（wqs二分）
先以一道题康康wqs二分要干什么：P2619 [国家集训队2]Tree I
设f(x)表示有x条白边的最小代价，如果按照x为横坐标，f(x)为纵坐标画图，会得到一个斜率递增的凸包
简单证明：考虑f(x+1)-f(x)的变化情况，也就是增加一条白边。因为要求的是最小代价，所以新增一条白边，一定是在当前没有被选入的白边中选一条最小的，那么就说明了形成的这个图像斜率时是递增的
由贪心可知，显然存在一个极值点k，使得x=k取得最小值，即对于x\in [1,m]:f(x)\geq f(k)，由费马引理可知，这一点的导数为0
又因为斜率是不断递增的，所以极值点k的左半部分斜率小于0，右半部分大于0，所以是一个斜率递减的凸包
考虑二分一个权值mid，表示用斜率为mid的直线去切这个凸包。因为这是一个下凸包，所以当直线切凸包的截距最小时，肯定是切于某个点(x,f(x))，设这个最小截距为g(mid)
那么有：\displaystyle f(x)=mid\times x+g(mid)，即g(mid)=f(x)-mid\times x
相当于x个数，每个数加了一个附加权值-mid
考虑g(mid)的实际意义，也就是g(mid)=\min\{f(x)-mid\times x\}，即x能够取遍全集，也就是没有数量的限制了
因为要求的是f(x)，f(x)并不好求，那么求出x和g(mid)就能够求出f(x)
同时因为这是一个凸包，当mid往一个方向改变时，x也是单调的改变，所以就可以二分了
当然，有的时候存在二分不出mid的情况，也就是凸包上存在三点共线的情况，这时候加上一些特殊的限制就好了：在这题就是边权相同时优先选择白边
然而这道题貌似并不是DP，来一道wqs二分优化DP的模板
CF739E Gosha is hunting
暴力DP：\displaystyle f[i][t_1][t_2]表示前i个宝贝，分别用了t_1,t_2个球的最大期望值
f[i][t1][t2]=f[i-1][t1][t2];
if(t1) f[i][t1][t2]=max(f[i][t1][t2],f[i-1][t1-1][t2]+p[i]);
if(t2) f[i][t1][t2]=max(f[i][t1][t2],f[i-1][t1][t2-1]+q[i]);
if(t1&&t2) f[i][t1][t2]=max(f[i][t1][t2],f[i-1][t1-1][t2-1]+p[i]+q[i]-p[i]*q[i]);
设f(t_1)为用了t_1个球的最大价值，显然当t_1增大到t_1+1，f(t_1)增大的越来越小，因为概率大的肯定优先取，所以斜率递减，构成一个上凸包
二分出一个实数mid，让所有的p都减去mid，如果求得的x小于a，缩小mid，反之扩大
这样时间复杂度就是O(\log n\times n^2)
然后发现里面也是完全类似的一个对个数的限制，所以可以再套一个wqs二分，复杂度就是O(n\log ^2n)
#include <iostream>
#include <cstdio>
using namespace std;
const int N=2010;
const double eps=1e-6,INF=1e18+10;
int n,a,b;
double res;
double p[N],q[N],r[N];
struct dp
{
int x,y;
double val;
}f[N];
inline bool check2(double slp)
{
for(int i=1;i<=n;i++) q[i]-=slp,r[i]-=slp;
f[0]=(dp){0,0,0};
for(int i=1;i<=n;i++)
{
f[i]=f[i-1];
if(f[i-1].val+p[i]>f[i].val) f[i]=(dp){f[i-1].x+1,f[i-1].y,f[i-1].val+p[i]};
if(f[i-1].val+q[i]>f[i].val) f[i]=(dp){f[i-1].x,f[i-1].y+1,f[i-1].val+q[i]};
if(f[i-1].val+r[i]>f[i].val) f[i]=(dp){f[i-1].x+1,f[i-1].y+1,f[i-1].val+r[i]};
}
for(int i=1;i<=n;i++) q[i]+=slp,r[i]+=slp;
return f[n].y>=b;
}
inline bool check1(double slp)
{
for(int i=1;i<=n;i++) p[i]-=slp,r[i]-=slp;
double low=0,high=1;
while(low+eps<high)
{
double mid=(low+high)/2;
if(check2(mid)) low=mid;
else high=mid;
}
check2(res=low);
for(int i=1;i<=n;i++) p[i]+=slp,r[i]+=slp;
return f[n].x>=a;
}
int main()
{
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<=n;i++) scanf("%lf",&p[i]);
for(int i=1;i<=n;i++) scanf("%lf",&q[i]);
for(int i=1;i<=n;i++) r[i]=p[i]+q[i]-p[i]*q[i];
double low=0,high=1;
while(low+eps<high)
{
double mid=(low+high)/2;
if(check1(mid)) low=mid;
else high=mid;
}
check1(low);
printf("%.4lf",f[n].val+low*a+res*b);
return 0;
}