听周神讲完，对此有些新的理解吧
证明决策单调性，不会四边形不等式也没关系
先以经典题P2900 [USACO08MAR]Land Acquisition G/土地购买为例。
[f[i]=min{f[j]+y[j+1]*x[i]}
]
用 (g[i]) 表示转移到 (f[i]) 最优的决策点，证明 (g[i]<=g[i+1]) ：
根据 (g[i]) 的定义，相当于已知了（下面 (j) 为任意决策点）
[f[g[i]]+y[g[i]+1]*x[i]≤[j]+y[j+1]*x[i]
]
那等价于证明：
[f[g[i]]+y[g[i]+1]*x[i+1]≤f[j]+y[j+1]*x[i+1] (j≤g[i])
]
利用已知：
(f[g[i]]+y[g[i]+1]*x[i+1]+y[g[i]+1]*(x[i]-x[i+1])≤f[j]+y[j+1]*x[i+1]+y[j+1]*(x[i]-x[i+1]))
(∵j≤g[i] ∴y[g[i]+1]≤y[j+1])
(∵x[i]<x[i+1] ∴x[i]-x[i+1]<0)
(∴y[g[i]+1]*(x[i]-x[i+1])≥y[j+1]*(x[i]-x[i+1]))
(∴f[g[i]]+y[g[i]+1]*x[i]<=f[j]+y[j+1]*x[i])
2D1D和1D1D
不过我好像也不是很清楚
但1D1D似乎是可以用斜率优化的，2D1D只能二分或者分治？