决策单调性优化DP

又是优化DP，孩子人都傻了。

什么是决策单调性

如果有(dp_i=minlimits_{j < i}(dp_j+delta_{j,i}))

并保证对于(forall i,j(i<j))，有(exists k)，使得(forall posinleft[0,kight],dp_i+delta_{i,pos}le dp_j+delta_{j,pos})且(forall posin(k,n],dp_i+delta_{i,pos}>dp_j+delta_{j,pos})，则说明决策有单调性。

（不就是说某个位置之前的点用(i)转移更优，而之后的点用(j)转移更优嘛）

如何判断是否满足决策单调性

1.满足四边形不等式的一定满足决策单调性

( ext{想起}leftlceil ext{四边形不等式}ightfloor)：(forall p_1le p_2le p_3le p_4)，有(delta_{p_1,p_3}+delta_{p_2,p_4}le delta_{p_1,p_4}+delta_{p_2,p_3})

然后发现( ext{四边形不等式}Rightarrow ext{决策单调性})，通了反证法。

[若i<j<k_1<k_2
]