好久没做过了
其有两种形式：
1.1d/1d dp\(f_i=\min(f_j+w(j+1,i))\)
它的特点是对于决策点\(a,b\)，\(a<b\)，如果\(a\)转移到\(c\)比\(b\)转移到\(c\)差，则以后\(a\)转移到\(d\)永远比\(b\)转移到\(d\)差
这说明决策点是单调递增的。
\(a<b<c<d,f_b+w(b+1,c)\leq f_a+w(a+1,c)\)
如果\(w(b+1,d)+w(a+1,c)\leq w(a+1,d)+w(b+1,c)\)
两者相加
\(f_b+w(b+1,d)\leq f_a+w(a+1,d)\)
证明成功。
实际上，决策点也可以单调递减。
它有两种求法：
分治法：类似整体二分。
如果要从数组\(c\)转移到\(d\)，代码如下：

void fz(int *c,int *d,int l,int r,int a,int b){
	if(l>r)
		return;
	int md=(l+r)/2,ans=l;
	for(int i=l;i<=min(md,b);i++){
		if(d[md]>c[i-1]+va(i,md)){
			d[md]=c[i-1]+va(i,md);
			ans=i;
		}
	fz(c,d,l,md,a,ans);
	fz(c,d,md+1,r,ans,b);
}

\(ans\)事实上代表\([l,md]\)最大转移点
根据决策单调性的定义，右边\([md+1,r]\)区间的转移点肯定大于等于\(ans\)，所以决策点被锁定到了\([l,md],[md+1,r]\)两个区间内。
分治法的优点：
1.好写好理解，不容易出错
2.如果\(va\)函数不容易求出，但是它移动一格容易求出（比如区间逆序对函数，直接做只能\(O(\sqrt{n})\)，但是移动一格可以用bit维护）
那么\(va\)函数总移动次数是\(O(n\log_2n)\)的。
缺点：只能从\(c\)转移到\(d\)，如果做1d/1d转移需要cdq分治，复杂度更高
二分+队列法
逆向思维

事实上，如果dp满足决策单调性，那么它关于选择的段数是凸的。
Itst的博客中有证明。
例题：
1.lg5574
容易列出方程\(f_{k,i}=\min(f_{k-1,j})+w(j+1,i)\)
可以证明\(w\)满足四边形不等式
但是事实上发现\(w\)很难快速求出，所以不能二分+队列。
但是它移动一格相当于查询一个区间内\(<v,>v\)的值的个数
用bit维护
2.CF868F
还是容易列出方程\(f_{k,i}=\min(f_{k-1,j})+w(j+1,i)\)
可以证明\(w\)满足四边形不等式。
但是事实上发现\(w\)很难快速求出，所以不能二分+队列。
移动一格相当于查询一个区间\(=v\)的值的个数
用桶维护，每次移动时加/减桶对应的那一位即可。
3.诗人小G
模板题
4.IOI2014 holiday
5.JOISC2019 蛋糕拼接
6.Mowing Mischief
7.记忆的轮廓
8.交与并
9.柠檬
10.jzoj5427
11.monster
12.Post加强版
13.环状邮局
14.uoj285
15.shoes
16.lg6932
17.lg6918