四边形不等式优化

[Ir1d]

https://oi-wiki.org/dp/opt/quadrangle/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[onlypath]

感觉 a,b,c,d 比 l1,l2,r1,r2 更适合初学者学习（比较容易想到四者的大小关系，而且满屏相似的字母和下标很容易让人头晕/yun）。。。

[greenstripes4]

能否也解释一下在相同的f和w函数情况下（可以简化w为四边形恒等式），为什么min计算可以使用四边形优化，而max不可以。网络搜索问题，只能看见一句话说max不单调，但是具体如何得到max不单调我一直没想明白。

[Himemushi884]

如果是max，你要直接套用四边形不等式，需要的是反号的四边形不等式。如果max还是相交小于包含，等价于min的情况是相交大于包含，这个东西是可以推出结论的，在某些场景下是有用的（比如CF1965F Conference，可以把一个 n^2log 的dp做法优化到 nlogn，以及这个做法实际上强于这个题，我拿去推广了一下出了个校赛题），但是跟单调性没什么关系，相反是对实际的方案的结构的描述。

[IdkWhatIsIdk]

ACM ICPC World Finals 2017 - Money

难道不是叫 Money For Nothing 吗

[WineChord]

好奇问下，所谓 1d1d 和 2d1d 有什么严格表示的含义吗？两个 d 中第一个 d 代表的是维度，第二个 d 表示的是？有没有 2d2d？

[hiya-arrrrr]

xDyD 表示狀態數量複雜度是 O(N ^ x)，計算出一個狀態的複雜度是 O(N ^ y)

[FollowTheWind-new]

二分队列的源代码好像有问题：应该在
//入队
这一行前面添加lt[dq.front()] = j;
不然的话，后面的val(j, lt[dq.front()]）会出现问题。

[WQhuanm]

请问决策单调性需要满足的条件是w函数具有单调性，但是w是单调增，还是单调减，是没有影响的吗。还是说求min时，需要满足单调减（大区间w值大，小区间小），而求max时，需要满足w函数单调增

[0x79ff]

二分队列的核心代码中以下分支有问题：

else if (val(j, rt[dq.back()]) < val(dq.back(), rt[dq.back()])) {
    if (rt[dq.back()] < n) {
      dq.emplace_back(j);
      lt[j] = rt[dq.back()] + 1;
      rt[j] = n;
    }

应改为

else if (val(j, rt[dq.back()]) < val(dq.back(), rt[dq.back()])) {
    if (rt[dq.back()] < n) {
      lt[j] = rt[dq.back()] + 1;
      rt[j] = n;
      dq.emplace_back(j);
    }

[YutaFanyuX]

不应该这样改吧，应该只要把 < 改成 > 就好了吧

[YutaFanyuX]

不对我在说什么，后面的也要改

[YutaFanyuX]

实测按我的写法是对的

[ljy2009]

这里“二阶混合差分非正”就是指在两维上分别具有单调性

[c-forrest]

不是噢，它指的是两个维度的相互作用。如果您对导数的语言比较熟悉，二阶混合差分就是交叉偏导数，从它的符号无法确定一阶导数的符号（即单个维度上的单调性）。