关于斜率优化
  • 板块学术版
  • 楼主konyakest
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/2/6 17:14
  • 上次更新2023/10/24 01:32:45
查看原帖
关于斜率优化
482660
konyakest楼主2023/2/6 17:14

本蒟蒻自己总结的斜率优化问题是:

转移方程式为 dpi=a(i)b(j)+c(j)+d\displaystyle dp_i=a(i)b(j)+c(j)+d 的dp,其中a、b、c为 O(1)O(1) 可求的函数,d 为关于 i 的函数或者常数

为此,为了避免重复思考,本蒟蒻还总结了模板:https://konyakest.blog.luogu.org/xie-shuai-you-hua-di-san-zhong-jing-jie

但是,今天看到一道题,列出状态转移方程式之后我蒙了

思路是这样

看起来不能转化为 dpi=a(i)b(j)+c(j)+d\displaystyle dp_i=a(i)b(j)+c(j)+d 的形式

但后来,另一篇体解说可以单调栈去掉多余土地后再转移,就可以化为这个形式了

现在问一下,所有的斜率优化都可以通过某种方式化为 dpi=a(i)b(j)+c(j)+d\displaystyle dp_i=a(i)b(j)+c(j)+d 的形式吗?

2023/2/6 17:14
加载中...