蒟蒻求助决策单调性优化
  • 板块学术版
  • 楼主「 」
  • 当前回复14
  • 已保存回复14
  • 发布时间2020/8/12 07:42
  • 上次更新2023/11/6 20:35:31
查看原帖
蒟蒻求助决策单调性优化
72468
「 」楼主2020/8/12 07:42

已知决策单调性优化必须满足四边形不等式:

w(a,c)+w(b,d)w(a,d)+w(b,c)w(a,c)+w(b,d) \le w(a,d)+w(b,c) (a<b<c<d)(a<b<c<d)

那如果说如果一道题目的 ww 正好与四边形不等式的式子相反,即:

w(a,c)+w(b,d)w(a,d)+w(b,c)w(a,c)+w(b,d) \ge w(a,d)+w(b,c)

然后我们给他两边都取一个反:

w(a,c)w(b,d)w(a,d)w(b,c)-w(a,c)-w(b,d) \le -w(a,d)-w(b,c)

然后我们如果设 g(i,j)=w(i,j)g(i,j)=-w(i,j),将题目要求的最大值(最小值)变为最小值(最大值), gg 就满足四边形不等式了。

所以说用这种方法可以使得原 dpdp 方程获得决策单调性优化???

还有,如果满足的话,那为什么原 dpdp 方程不满足而取反后的式子就满足了呢?因为将 ww 数组和目标都取反的话好像跟直接做没什么区别啊……

2020/8/12 07:42
加载中...