Stephen Horizon
Stephen Horizon

「OI笔记」四边形不等式

前言

  2021.8.26总结附属产品(doge

正文

定义

  对于任何

https://pro.goforit.top/stephen-zeng/img/master/202108261.png

都有
https://pro.goforit.top/stephen-zeng/img/master/202108262.png

这个东东就叫四边形不等式。

性质

  对于如下方程

https://pro.goforit.top/stephen-zeng/img/master/202108263.png

这里有两个定理

1.

  首先介绍这个:

包含单调性

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

https://pro.goforit.top/stephen-zeng/img/master/202108264.png

比如
https://pro.goforit.top/stephen-zeng/img/master/202108265.png

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

2.

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

https://pro.goforit.top/stephen-zeng/img/master/202108266.png

若函数f为四边形不等式,那么g函数具有单调性:
https://pro.goforit.top/stephen-zeng/img/master/202108267.png

理解

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

https://pro.goforit.top/stephen-zeng/img/master/202108267.png

蓝线长和≤红线长和

应用

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

https://pro.goforit.top/stephen-zeng/img/master/202108265.png

  但是,求最大值不可以,因为他不满足单调性。
  所以,具体的做法还是看题解吧,我也是看了TA的文章才搞懂四边形不等式的。

总结

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

Stephen Zeng

文章作者

发表评论

textsms
account_circle
email

Stephen Horizon

「OI笔记」四边形不等式
前言   2021.8.26总结附属产品(doge 正文 定义   对于任何 都有 这个东东就叫四边形不等式。 性质   对于如下方程 这里有两个定理 1.  &…
扫描二维码继续阅读
2021-08-26