已知决策单调性优化必须满足四边形不等式:
w(a,c)+w(b,d)≤w(a,d)+w(b,c) (a<b<c<d)
那如果说如果一道题目的 w 正好与四边形不等式的式子相反,即:
w(a,c)+w(b,d)≥w(a,d)+w(b,c)
然后我们给他两边都取一个反:
−w(a,c)−w(b,d)≤−w(a,d)−w(b,c)
然后我们如果设 g(i,j)=−w(i,j),将题目要求的最大值(最小值)变为最小值(最大值), g 就满足四边形不等式了。
所以说用这种方法可以使得原 dp 方程获得决策单调性优化???
还有,如果满足的话,那为什么原 dp 方程不满足而取反后的式子就满足了呢?因为将 w 数组和目标都取反的话好像跟直接做没什么区别啊……