DP提高笔记
数位 DP
即为对数字的每一位来进行 DP。
例 1：
给定两个正整数 $a$ 和 $b$，求在 $[a,b]$ 中的所有整数中，每个数码各出现了多少次。
很明显，直接套数位 DP 的模板即可：
1 | void dfs(ll pos,ll num,...,bool limit,bool lead){ |
例 2：
求满足下列所有条件的4元组（整数） 数量：
$a+c > b+d,a+d \ge b+c,0 \le a \le A,0 \le b \le B,0 \le c \le C,0 \le d \le D$（$0 \le A,B,C,D \le 10^{18}$）
还是套模板，但是此处涉及到了加法，那么很显然要再开一维表示进位，然后会发现 TLE，因为一次转移跟 $d$ 有很大的关系，考虑转化为 $2$ 进制，发现还是 TLE，原来 $limit$ 和 $lead$ 浪费的时间太多了，那么直接存在 dp 状态里面就可以了。
例 3：[SCOI2013] 数数
先套模板，然后会发现数位和会 TLE，但是发现 $i=0,i=up$ 和 $1 \le i < up$ 分别都是相同的转移，然后去除无用状态和循环即可。
例 4：
对 $1$ 个 $10$ 进制数，定义它的众数为所有数位中出现次数最多的数字d，特别的，若出现次数最多的数字有多个，则认为众数不存在，例如，$114514$ 的众数为 $1$；$4396$ 则不存在众数，求 $[l,r]$ 中众数为 $d$ 的数字数量。
对于每个 dfs 状态，然后如果 $limit=0$ 那么可以直接通过每个数出现的次数 dp 出来结果。
还要处理前导 $0$，那么一次询问就是 $18 \times 18 \times 10^3$ 左右的，但是我们发现对于一个数 $\overline{abcde\cdots }$，其所有 $0 \sim 99999\dots 999$，位数到达 $b$ 的位置都可以预处理得到。
故时间复杂度少了一个 $18$，即可通过。
例 5：[SDOI2013] 淘金
考虑数位 dp 的模板，额外记录当前乘积中 $2,3,5,7$ 的因子个数，然后发现总状态只有 $8 \times 10^3$ 左右个，然后暴力地执行 dp 最后跑一下二路归并即可。
总结：
- 如果 dp 过程中在 $limit=0$ 的时间可以 $O(d)$ 得出答案，那么一共可以在 $O(d \times T \times \text{位数}^2)$ 的时间复杂度内算出答案，如果可以记忆化可以少一个位数的时间复杂度。
- 有些状态是完全重叠的，那么我们直接合并就可以优化时间复杂度。
- 做数位 dp 应该像普通 dp 那样寻找重叠的子任务，然后合并而不是只套模板。
斜率优化
斜率，直线上任取两点 $(x_1,y_1),(x_2,y_2)$ 的 $\dfrac{y_2-y_1}{x_2-x_1}$。
主要应用于形如下式的 1D/1D 动态规划：
$$
f_i = \min/\max{f_j+a_i \times b_j+c_i+d_j}
$$
遇到这种情况可以选择斜率优化，李超线段树的写法在这里不做详解。
斜率优化具体而言是维护一个凸包，形如下图（左边是下凸包，右边是上凸包）
对于一般的题目都是要求截距 （$y=kx+b$ 中的 $b$）最小/大化，故此处对斜率最小/大化，不过多讲解，但是都可以互相转化。
凸包的特点就是每条线段的斜率都是单调的，且上下凸包恰好相反。
考虑在凸包上加点：
如果加的点的 $x$ 坐标单调不降，那么我们可以动态维护凸包，即使用单调栈，判断线段的斜率即可。
如果加的点的 $x$ 坐标非单调，那么我们需要用 CDQ 分治强制让它单调，然后处理左边对右边的贡献就可以了。（左边按 $x$ 排序，右边按斜率排序就可以处理了，还有要记住添加的顺序不能打乱）
考虑点的斜率：
- 如果斜率单调不降，那么它具有决策单调性，可以把前面的全部弹出去直到最小/大的那个，而且同时保证了后面的点的决策正确性。
- 否则需要在凸包上二分，二分哪个点最优，我们发现，对于下凸包而言（上凸包类似），所有点到当前决策点的线的截距一定是形如 $a_1 > a_2 > \dots >a_i < a_{i+1} < \dots < a_k$，二分这个符号，找到最后一个大于即可。
综上：
| $x$ 单调不下降 | $k$ 单调不下降 | |
|---|---|---|
| 是 | 单调栈 | 决策单调性 |
| 否 | CDQ分治 | 单调队列上二分或者CDQ分治 |
注意：
- 如果碰到 $x$ 相同的两个节点，那么如果是维护最小值的话，要丢弃 $y$ 较大的，否则丢齐较小的。
最后就是一定要把 $x,y,k$ 的公式列出来，对于斜率优化而言，上述 dp 方程中：$x=b_j,y=f_j+d_j,k=a_i$，把 $j$ 这个点加到凸包里面，然后对于 $i$ 来说用斜率为 $k$ 的直线去截取凸包就可以了。
特别的，李超线段树恰好相反。
有时候一个等于号就能够改变整个代码的逻辑，写代码的时候一定要注意。
四边形不等式
统一地来说，若一个函数 $w(a,b)$ 满足下列条件则称 $w$ 函数满足四边形不等式。
$$
w(a,c)+w(b,d) \le w(a,d)+w(b,c)(a \le b \le c \le d)
$$
通常用来解决决策单调性的问题。
1D/1D 动态规划
若我们可以写成 $f_i = \min{f_j+w(i,j)}$ 的形式，且 $w$ 函数满足四边形不等式，则称 $f$ 函数具有决策单调性。
或者 $f_i = \max{j+w(i,j)}$ 但是 $w$ 函数满足交叉大于包含，也可以用决策单调性。
即设 $f_i$ 是由 $f_{k1}$ 转移过来且 $f_j$ 是由 $f_{k2}$ 转移过来，那么若 $i>j$ 那么 $k1 \ge k2$。
此处证明略。
$w$ 函数与 $f$ 没有关系
如果满足上面的条件的话，那么我们可以用整体二分法求解。
即函数 $\operatorname{solve}(l,r,s,t)$ 表示 $f_{l \sim r}$ 的决策点一定都是在 $s \sim t$ 内的。
那么我们每次转移的时候就取中间点，然后分为两部分递归下去就行了，特别的，如果 $w_{l,r}$ 必须通过 $O(n)$ 的方式得到，那么我们可以在函数的过程中添加一个莫队的指针移动，这样的话时间复杂度是严格 $O(n \log n)$ 的。
$w$ 函数与 $f$ 有关系
我们考虑单调队列存储三元组 $(l,r,p)$，表示所有 $dp_{l \sim r}$ 的转移点，都是 $p$，如果我们添加进来了一个新的转移点，那就比较如果在 $dp_l$ 地方是这个新的转移点较优，那 $dp_{l \sim r}$ 一定都选这个转移点，直接 $\operatorname{pop}$ 即可；否则需要二分找到一个临界点 $k$，使得 $dp_{l \sim k}$ 的转移点都是原来的 $p$，然后 $dp_{k+1,r}$ 的转移点是新的转移点，然后 $\operatorname{push}$ 进单调队列即可。
最后如果队头的 $r<$ 当前决策点 $i$，直接弹出即可，时间复杂度 $O(n \log n)$。
其它
当然还有 $w$ 函数，满足四边形不等式，但是符号相反，即四边形不等式和 dp 转移符号相反。那样的话需要用到单调栈维护。
栈顶到栈低一定也是三元组 $(l,r,p)$，且 $l,r$ 递增。（$l$ 和 $r$ 有可能会发生变化，因此不存下来，而是要用的时候二分求解）
此处就不再赘述了，大概就是先看栈头的两个元素的分界点是不是小于 $i$，如果小于就弹出，最后把 $i$ 更新之后加入到栈里面，且满足决策点递增。（决策点如果不递增就直接弹出栈顶）
解释：详见 Fiyuls 博客，很详细。
2D/1D 动态规划
形如 $dp_{l,r} = \min{dp_{l,k}+dp_{k+1,r}+w(l,r)}$ 的转移且 $w$ 函数满足四边形不等式和区间单调性（$w(a,b) \ge w(c,d) (a \le c \le d \le b)$，那么 $dp_{l,r}$ 也具有决策单调性。
遇到这种情况，把每个决策点存下来，然后 $dp_{l,r}$ 的最优决策点一定在 $dp_{l,r-1}$ 的最优决策点和 $dp_{l+1,r}$ 的最优决策点之间，然后 for 循环枚举即可。
注意到每一种区间长度的枚举总数一定不超过 $2n$，所以整个时间复杂度是 $O(n^2)$。
常见的问题就是优化石子合并。
动态 DP
用线段树维护矩阵转移。
主要是一些树上 dp 被弄上了修改点权的操作。
把 dp 用广义矩阵乘法写出来，然后再来一个 $g$ 数组表示去掉重儿子的答案，再搞一个 $f$ 数组表示直接答案。
$g$ 的转移矩阵一定得用关于 $x$ 和其儿子的变量表示出来（常数），然后 $f$ 一定能用 $g$ 和重儿子的信息表示出来（常数）。
最后树链剖分维护一下每条重链的信息就可以了。
注意：
- 矩阵常数优化可以拆开乘法的过程。
- 每条链可以单独开一个线段树，这样节省了很多时间。
- 此处树链剖分时，线段树每个节点存储的是一段矩阵乘法。
- 特别注意叶子节点的边界情况，一般是“单位矩阵”。