有一部分题目是模板题，就不放了。
D. Luogu-P5336 THUSC 2016 成绩单
考虑区间 DP，由于操作的特殊性，我们需要设计含有区间最值的状态，设 \(f_{l,r,i,j}\) 表示区间 \([l,r]\) 中的所有数只保留值域 \([i,j]\) 中的最小代价，\(g_{l,r}\) 为将区间 \([l,r]\) 的所有数都删去的最小代价。
\(g_{l,r}\) 的转移非常简单，就是直接枚举最后删的区间，设值域为 \([1,m]\)，方程：
\[g_{l,r}=\min_{1\le i\le j\le m}\{f_{l,r,i,j}+a+b(j-i)^2\} \]而 \(f_{l,r,i,j}\) 是枚举断点，左右区间可以选择直接删去或是变成子问题：
\[f_{l,r,i,j}=\min_{p=l}^{r-1} \{\min(g_{l,p}+f_{p+1,r,i,j},f_{l,p,i,j}+g_{p+1,r},f_{l,p,i,j}+f_{p+1,r,i,j})\} \]提交记录：Submission - Luogu
H. AtCoder-AGC034_E Complete Compress
考虑判定，设 \(f_u\) 为 \(u\) 子树内所有棋子到 \(u\) 的距离和，那么当 \(f_u\) 为偶数时，答案是 \(\frac{f_u}{2}\)。但是当某个子树贡献的 \(f\) 很大时，可能无法在 \(u\) 位置集合。
每个子树内部可以自己“消化”一些距离，考虑求出 \(g_u\) 表示 \(u\) 子树内部“消化”能得到的最小距离和（即选择子树内的两个节点靠近不计入这里的距离）。那么最小的情况就是将 \(f\) 贡献最多的节点尽量减少。比较 \(2\max_{v \mathrm{son}(u)}\{f_v+siz_v\}\) 与 \(\sum_{v\in \mathrm{son}(u)} f_v+siz_v\) 即可，若 \(v\) 子树贡献超过一半，而 \(v\) 子树改为贡献 \(g_v\) 时贡献小于一般，则 \(g_u=0\)，否则 \(g_u\) 为 \(v\) 的贡献与其他子树贡献的差。
判定就是 \(g_u\) 是否为 \(0\)，使用换根 DP 即可。
提交记录：Submission - AtCoder
M. UniversalOJ-140 UER#4 被粉碎的数字
考虑数位 DP，范围是 \([1,kR]\) 中所有 \(k\) 的倍数。状态需要考虑模 \(k\) 的余数和当前 \(f(kx)-f(x)\) 的值，设 \(f(i,p,b,0/1)\) 表示考虑第 \(i\) 位，当前模 \(k\) 的余数是 \(p\)，且已经确定的 \(f(kx)-f(x)=b\) 的方案数，\(0/1\) 是上界的限制。
转移枚举 \(kx\) 这一位上数 \(d\)，那么转移到的状态 \(p'=(10p+d)\bmod k,b'=b+\left(d-\left\lfloor\frac{10p+d}{k}\right\rfloor\right)\)。
P. CodeForces-1067D Computer Game *3100
暑假模拟赛题。
第一次升级一定会选择最大的 \(v=p_ib_i\) 升级，之后只选这个操作，这样的期望得分最高。
倒序 DP，设 \(f_t\) 为还剩 \(t\) 次操作时的期望最大值，转移是枚举进行哪个操作，并讨论成功与否。
\[f_t=\max_{i=1}^n \{p_i(a_i+(t-1)v)+(1-p_i)f_{t-1}\} \]考虑优化，整理发现符合斜率优化形式：
\[-p_ia_i=((t-1)v-f_{t-1})p_i+(f_{t-1}-f_t) \]要求 \(f_t\) 最大，即截距最小，那么有 \(X_i=p_i,Y_i=-p_ia_i\)，维护一个下凸壳，可以单调栈预处理出，每次二分。
由于最优情况每次 \(f\) 增加 \(t\)，所以 \((t-1)v-f_{t-1}\) 实际上不降。
考虑优化，\(t\) 很大，所以使用矩阵加速：
\[\begin{bmatrix}f_{t-1}&t-1&1\end{bmatrix}\times \begin{bmatrix}1-p_i&0&0\\p_iv&1&0\\p_ia_i&1&1\end{bmatrix}=\begin{bmatrix}f_t&t&1\end{bmatrix} \]这样能二分一个在 \(i\) 处转移的区间来处理，时间复杂度 \(O(k^3n\log^2 t)\)，改为倍增判断即可 \(O(k^3n\log t)\)。需要细致处理精度。
标签：12,Submission,乱写,省选,枚举,子树,bmatrix,区间,DP From： https://www.cnblogs.com/SoyTony/p/DP_Training_Problems_of_Provincial_Team_Selection_in_Bei