CF721C Journey
以答案代状态。
P3251 [JLOI2012] 时间流逝
树上高消，式子化为 \(f(u)=k\cdot f(pr)+b\) 形式。
P3259 [JLOI2014] 路径规划
最短路带特定点的数量限制时，使用分层图最短路。
P3980 [NOI2008] 志愿者招募
对于一个点，它会影响到接下来的点，故将所有的点串联起来。一个线段，就连接两个端点，费用为价格。
对于容量的设置，由于是“至少”，故将边权设为负，再整体平移。
如果是“至少”，用正边权即可。
“麻将”（\([i,i+1,i+2][i,i,i]\)）
DP 时在状态中记录 \([i-1,i,i+1]\) 与 \([i,i+1,i+2]\)，数量不超过 \(2\)。
CF1110D Jongmah
\[f[i][k][l]\gets f[i-1][j][k]+\lfloor\frac{C_i-j-k-l}{3}\rfloor+l \]P5371 [SNOI2019] 纸牌
观察到 \(10^{18}\) 与矩阵乘法形式，使用矩阵乘法优化。
特殊位置数量少，处理时，将式子对应位置的矩阵替换掉，然后再合并相同的。（即 ksm, mul, ksm, mul, ksm...）
P5279 [ZJOI2019] 麻将
对于状态 \(f[i][j][k][0/1]\)，发现有无用的，则将 \([j][k][0/1]\) 提出，构建自动机，做 DP 套 DP。
Slope Trick
CF713C Sonya and Problem Wihtout a Legend
严格增，以 \(a_i\gets a_i-i\) 转为不降。
设 fi,j 表示将 ai 变成 j，使得 [1,i] 的数列不降所需要的最小操作次数，那么有：fi,j = min1≤k≤j(fi−1,k)+∣ai −j∣
记 Fi(x) 为 fi,x，发现 Fi 下凸。
二维数点问题
一般用扫描线解决。
比如矩形加查。
P3242 [HNOI2015] 接水果
树上的一条路径 \(x,y\) 转化为点 \((\text{dfn}_x,\text{dfn}_y)\)。路径包含其它路径转化为点被矩形包含（见题解），套整体二分，转化为矩形加单点查。
标签：套路,路径,矩阵,fi,ksm,一些,填写,矩形,DP From： https://www.cnblogs.com/Zaunese/p/20230807--taolu.html