📚【模板】决策单调性优化DP

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

创新互联建站是专业的韶关网站建设公司，韶关接单;提供成都网站建设、网站制作,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行韶关网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

什么是决策单调性

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

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

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

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

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

\(\text{想起}\left\lceil\text{四边形不等式}\right\rfloor\)：\(\forall p_1\le p_2\le p_3\le p_4\)，有\(\delta_{p_1,p_3}+\delta_{p_2,p_4}\le \delta_{p_1,p_4}+\delta_{p_2,p_3}\)

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