「OI笔记」四边形不等式

前言

2021.8.26总结附属产品（doge

正文

¶定义

对于任何 都有 这个东东就叫四边形不等式。

¶性质

对于如下方程 这里有两个定理

¶1.

首先介绍这个：

¶包含单调性

若方程满足以下性质，则该方程有包含单调性。 比如

若w满足包含单调性和四边形不等式的定义，那么f也是四边形不等式

¶2.

我们设g为f取值为最佳时对应的值： 若函数f为四边形不等式，那么g函数具有单调性：

¶理解

或许，我们可以换种方式理解四边形不等式，同时知道这个东西为什么叫四边形不等式。 蓝线长和≤红线长和

¶应用

这东西主要是加快DP的速度，减少无用的循环次数。针对对象正如上文的函数f一样。如 P1880 NOI1995 石子合并 这道题中求最小值的dp函数可以用四边形不等式优化，而且正好他的w函数就是本文的g函数   但是，求最大值不可以，因为他不满足单调性。   所以，具体的做法还是看题解吧，我也是看了TA的文章才搞懂四边形不等式的。

总结

这应该算是DP里面一种比较基础的优化了吧，不管怎样，填坑+1。