动态规划——min/max的单调性优化总结

一般形式:

$max{min(ax+by+c,dF(x)+eG(y)+f)},其中F(x)和G(y)是单调函数。$

$min{max(ax+by+c,dF(x)+eG(y)+f)},其中F(x)和G(y)是单调函数。$

(以下用第一种形式讨论)

(1)dF(x)随ax的增大而增大,eG(y)随by的增大而增大。

ax和by均取最大值。

(2)dF(x)随ax的增大而增大,eG(y)随by的增大而减小。

ax一定取最大值,ax和dF(x)变成常数。

此时变成:

$H(y)=max{min(by+c,eG(y)+f)}$

H(y)是个单峰函数。

(3)dF(x)随ax的增大而减小,eG(y)随by的增大而增大。

与(2)类似。

(4)dF(x)随ax的增大而减小,eG(y)随by的增大而减小。

从小到大枚举ax,当ax变大时,dF(x)随着变小:

$max{min(ax↑+by+c,dF(x)↓+eG(y)+f)}$

如果by也跟着变大,那么eG(y)随着变小:

$max{min(ax↑+by↑+c,dF(x)↓+eG(y)↓+f)}$

由于我们取的是min,这样并没有什么卵用。

所以by只能变小。

$max{min(ax↑+by↓+c,dF(x)↓+eG(y)↑+f)}$

所以随着我们从小到大枚举ax,ay单调递减。

枚举ax时,ax和dF(x)变成常数。

此时变成:

$H(y)=max{min(by+c,eG(y)+f)}$

H(y)是个单峰函数。

原文地址:https://www.cnblogs.com/maijing/p/4701028.html