沙尘暴下的情景，在我 qzone 里有没对焦上的情景。
决策单调性
在 dp 转移中，设 $\operatorname{opt}(i)$ 为 $i$ 的决策转移点，若对于任意 $i<j$，有 $\operatorname{opt}(i)\le\operatorname{opt}(j)$，则称其具有 决策单调性。
四边形不等式
对于任意 $a\le b\le c\le d$ 满足 $w(a,c)+w(b,d)\le w(a,d)+w(b,c)$，那么称 $w$ 满足 四边形 不等式，通常记作「交叉小于包含」。
若上式永远成立，则对于 $f_i=\min\limits_{j\in[1,i]}w(j,i)+f_j$，$f$ 的转移满足 决策单调性。
优化手段
二分队列
可以在线。
队列元素形如 $(p,l,r)$，分别表示决策点以及其贡献到的区间 $[l,r]$，显然 $[l,r]$ 之间无交且并集为全集。
其队头为当前 $i$ 的决策转移点，那么显然必须满足 $i\in[l,r]$，于是当 $r<i$ 时不断弹出队首。
考虑当前元素对队尾的影响，队尾管辖区间右端点必然为 $r$。二分找到首个满足 $\operatorname{cost}(i,k)$ 优于 $\operatorname{cost}w(p_{tail},k)$ 的 $k$，若 $k\le l_{tail}$，那么队尾元素没用，直接删掉。否则令 $r_{tail}\gets k-1$，将 $(i,k+1,n)$ 入队。
见下面的一道例题。
P1912 [NOI2009] 诗人小G
给出 $n$ 个长度为 $a_i$ 的数，分成任意段，使 $\sum\limits_{k_i}\vert\sum\limits_{j\in(k_{i-1},k_i]}a_i-L\vert^P$ 最小。
设 $f_{i}$ 表示以 $i$ 结尾的答案，容易得到 $f_{i}=\min\limits_{j<i} f_{j}+\vert\sum\limits_{k=j+1}^ia_k-L\vert^P$，设后面这个东西为 $w(l,r)=\vert S_r-S_{l-1}-L\vert^P$。注意到这个函数一定是下凸的，所以满足四边形不等式。
然后就可以维护决策点了。
|
|
分治
离线，码量小。
分治时变量为 $(l,r,ql,qr)$，分别表示当前算的范围 $[l,r]$ 以及决策点范围 $[ql,qr]$。每次暴力枚举决策点缩小范围转移即可，下面是最小值最优的示范。
|
|
QOJ5507 Investors
给出序列 $a$，最多 $k$ 次操作选 $[l,r]$ 加正整 $x$，最小化最终逆序对数。 $k\le\vert a\vert\le 6000 $。
注意到对后缀加一定不劣，即每次对后缀进行 $+\infty$ 操作后一定能最小化，问题转化为将 $a$ 划分成 $k+1$ 段，使每个段单独贡献最小。
具体的，设 $f_{i,j}$ 表示前 $i$ 个数，一共划分成 $j$ 段的最小贡献。有 $f_{i,j}=\min\limits_{k<i}f_{k,j-1}+\operatorname{inv}(k+1,i)$，其中 $\operatorname{inv}(l,r)$ 表示区间 $[l,r]$ 的逆序对数，容易 $\mathcal O(n^2)$ 预处理，总的复杂度是 $\mathcal O(kn^2)$。
考虑优化，显然 $\operatorname{inv}(l,r)$ 可以拆成 $\operatorname{inv}(l, m)$ 与 $\operatorname{inv}(m+1,r)$ 和 $[l,m]$ 对 $(m,r]$ 的贡献，所以这个东西满足四边形不等式，于是就有决策单调性。
|
|