决策单调性&DP
preface
DP的决策单调性优化总结 - command_block 的博客
老早就听说了四边形不等式的大名，但听到的更多是"打表发现决策单调性，然后直接做..."，所以就学了一下...
本文将先介绍四边形不等式，斜率优化（特殊情况满足决策单调性），然后再进入正题
至于为什么不讲单调队列，其本身就是决策单调性的一种特殊情况
还有，决策单调性和凸性相关，所以常常可以配合wqs二分使用
四边形不等式
简称：交叉小于包含
\[a<b<c<d,w(a,c)+w(b,d)\le w(a,d)+w(b,c) \]\(w(i,j)\)表示从i转移到j的贡献
当w满足四边形不等式时，该DP具有决策单调性
而决策单调性到底是什么？它告诉我们，我们的转移点一定只会变大
斜率优化
\[f_i=(i)+\max\{f_j+(j)+(i')(j')\} \]\((i)(i')\)为与i有关的贡献
然后我们就把每个j看作\(((j'),f_j+(j))\)的点，维护个凸包，然后用斜率\(k=-(i')\)的斜线去切，计算答案
于是就涉及到两个单调性的问题
- \((j')\)是否有单调性，这决定着维护凸包是否用cdq或李超树
- \((i')\)是否有单调性，这决定着切凸包时用队列或是二分
当同时满足两个单调性时，该dp就有决策单调性，并且可以用简单的单调队列处理
当变成树形dp时，可能要求维护支持撤回的凸包，就需要可持久化李超树（其实全部的斜率优化都可以用李超树）
1D/1D
指状态数为n，转移为n的DP
通用做法——二分栈
如[P3515 [POI2011] Lightning Conductor]([P3515 POI2011] Lightning Conductor - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
给定一个长度为 \(n\) 的序列 \(\{a_n\}\)，对于每个 \(i\in [1,n]\) ，求出一个最小的非负整数 \(p\) ，使得 \(\forall j\in[1,n]\)，都有 \(a_j\le a_i+p-\sqrt{|i-j|}\)
\(1 \le n \le 5\times 10^{5}\)，\(0 \le a_i \le 10^{9}\) 。
简单转化题意，我们求的是
\[f_i=max_{j=1}^i a_j+\sqrt{i-j} \]发现开根满足四边形不等式，有决策单调性
如图，最优转移一直再向右，可以用二分栈维护，具体来说，一般用单调队列实现
我们维护一个单调队列，使得相邻的决策点的临界点递增（结合上图思考），然后如果到达队头的临界点，就弹出队头。每次再加入，保证单调性。找临界点用二分
2D/1D
指状态数为\(n^2\)，转移为n的DP，而且同层之间没有转移，只从上一层转移并有单调性
分治
考虑一种简单的做法，定义分治函数\(solve(l,r,ll,rr)\)，表示状态为\(l\sim r\)，决策点可能为\(ll\sim rr\)
然后每次暴力找到 \(mid\) 的决策点 \(k\) ，分治\(solve(l,mid-1,ll,k),solve(mid+1,r,k,rr)\)
时间复杂度和二分栈一样，多一个log
那么它的优势在哪？
将一个长度为 \(n\) 的序列分为 \(k\) 段，使得总价值最大。
一段区间的价值表示为区间内不同数字的个数。
\(n\leq 35000,k\leq 50\)
我们发现区间的贡献无法快速计算，它是莫队的经典例题
根据分治树美妙的形态，我们可以证明暴力跑莫队的时间复杂度还是log
void solve(int l,int r,int ll,int rr){
int mid=l+r>>1,k=0;
Fu(i,ll,min(rr,mid-1)){
while(x>i+1) add(--x);
while(y<mid) add(++y);
while(x<i+1) del(x++);
while(y>mid) del(y--);
if(f[mid]<g[i]+num) f[mid]=g[i]+num,k=i;
}
if(l==r) return ;
if(l<mid) solve(l,mid-1,ll,k);
if(mid<r) solve(mid+1,r,k,rr);
}
n^2做法
不建议使用，因为不知道什么时候可以使用，好像要满足一些类似区间DP的转移时才可以使用，否则时间复杂度是错误的
定义 \(f_{i,j}\) 的决策点为\(k_{i,j}\)，那么\(k_{i-1,j}\le k_{i,j}\le k_{i,j+1}\)
于是第二维倒着枚举就可以\(O(n^2)\)解决
[P4767 [IOI2000]邮局](https://www.luogu.com.cn/problem/P4767)
tips
有些贡献本身满足决策单调性，但进行max或取整后就不满足，所以要注意
标签：le,ll,决策,mid,单调,DP From： https://www.cnblogs.com/zhy114514/p/18258897