一般用 tD / eD 描述动态规划的规模，即有 O(nt) 个状态，每个状态通过 O(ne) 个子问题推出答案。
wqs 二分
决策单调性
我们首先介绍四边形不等式。假设要求解最小值，如果有转移 fj←fi+w(i,j)，且 w 满足四边形不等式，即若 a<b<c<d，则 w(a,d)+w(b,c)≥w(a,c)+w(b,d)，则具有决策单调性：随着 i 的增大，转移点 pi 不降。
证明
采用反证法，存在 pj<pi<i<j，那么：
fpi+w(pi,i)≤fpj+w(pj,i)fpj+w(pj,j)≤fpi+w(pi,j)
因此得到 w(pi,i)+w(pj,j)≤w(pj,i)+w(pi,j)，不满足四边形不等式。如果相等，说明两个不等式都是等式，pj 也可以转移到 i，那么 pi 不成立。
分治处理
直接套用分治可以 O(nlogn) 完成一层的转移，只要 w 可以直接计算或者增量计算即可。
[PtzS2020-6] Rhythm Game
Portal.
设 fi,j 代表前 i 个音符敲击 j 个？这样转移就需要枚举连续敲击之类的，不太方便。改为漏了 j 个，还是不太方便，因此强制钦定第 j 个漏了，这样可以在 n+1 算答案，正好统计最后的 P。
转移就是 fi,j←fk,j−1+w(k+1,i−1)，w 满足四边形不等式，证明容易做差得到。
值得注意的是，当 i>j 时，w(i,j) 是不满足四边形不等式的，但是转移的时候却会出现这种情况，因此要把 fi,dep←fi−1,dep−1 的转移单独拉出来。代码。
斜率优化
数据结构优化