关于四边形不等式
  • 板块学术版
  • 楼主uibn
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/1/11 14:40
  • 上次更新2023/10/28 12:31:18
查看原帖
关于四边形不等式
60215
uibn楼主2022/1/11 14:40

想这个问题很久了,就是在一维的dp中,满足决策单调性,用单调队列优化。这时每次求出一个fi,考虑i可以用来做那些点的最优决策,假设最后i可以做[l,r]范围内的最有决策点,但是在DP过程中,如果r+1当前的决策点比i好,就直接退出更新,即使r+1的最优决策点是i+1,但是它当前的点(比如可能是f1)却比i要好。这样不就出错了吗?

是四边形不等式还有什么别的性质吗,为什么这样做是可以的?

2022/1/11 14:40
加载中...