前言

  2021.8.26总结附属产品（doge

正文

定义

  对于任何

性质

  对于如下方程

1.

  首先介绍这个：

包含单调性

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

比如

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

2.

  我们设g为f取值为最佳时对应的值：

理解

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

应用

  这东西主要是加快DP的速度，减少无用的循环次数。针对对象正如上文的函数f一样。如
P1880 NOI1995 石子合并
这道题中求最小值的dp函数可以用四边形不等式优化，而且正好他的w函数就是本文的g函数

总结

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