决策单调性随笔

这个题让我入门了决策单调性（我爬了）。。。。。

说：谢谢出题人。

我：“谢谢出题人”。

首先，转化成 \(w_0+w_1,w_2,w_3,\cdots ,w_n\)。

然后有显然的 \((+,\min)\) 卷积，有:

\[ f_x=\min_{i+j=x}(h_i+g_j) \]

设 \(x\) 最优转移点是 \(p_x\)，通过四边形不等式，证明决策单调性。

\[ \begin{aligned} f_x=h_{p_x}+g_{x-p_x},&f_y=h_{p_y}+g_{y-p_y}\\ \text{if } x>y,&p_x<p_y:\\ h_{p_x}+g_{x-p_x}<h_{p_{y}}+g_{x-p_{y}} &,h_{p_y}+g_{y-p_y}<h_{p_x}-g_{y-p_x}\\ \Longrightarrow g_{x-p_x}+g_{y-p_y}<&g_{x-p_y}+g_{y-p_x} \end{aligned} \]

到这里，已经是四边形不等式的样子了： \(c(p_x,x)+c(p_y,y)<c(p_y,x)+c(p_x,y)\)

不难发现他说的是反的四边形不等式，\((p_x,x)\) 包含 \((p_y,y)\)。

包含<相交，矛盾了

所以满足四边形不等式即可。

所以此时 \(p_x>p_y\)。

移个项，\(g_{y-p_y}-g_{y-p_x}<g_{x-p_y}-g_{x-p_x}\)，

注意只需要保证 \(p_y<p_x<y<x\),因为如果 \(y<p_x\) 那么必定决策单调。

所以含义是 ：

\[\sum_{i=y-p_x+1}a_i<\sum_{i=x-p_x+1}a_i\]

也就是从 \(y-p_x+1,x-p_x+1\) 分别选 \(p_y-p_x\) 个，\(a\) 单调的话，显然，看成 \(g\) 就是 \(g\) 凸。

---

这里需要一些注意了，我们只需要保证 g 有着凸性，他的决策就有单调性。（换句话说，\(f\) 可以不具有凸性）

如果 g 没有完全凸性，可以（？）适当拆开合并？（我就做过一个在x=0 处拆开的）

---

值得注意的是：我们只是在说明对于原始转移点 \(a<b\)，不可能存在 \(c<d\)，\(b\) 转移到 \(c\) 优于 \(a\),但 \(a\) 转移到 \(d\) 优于 \(b\)。

同时也是这个支撑了整个“决策”单调性，只不过是普通转移，并非“决策”，转移要弱于决策，当然决策成立也可以说是转移的特性吧。

上面那句话说的是： \[ \begin{aligned} y<x,a<b\\ f_x+w(x,a)&<f_y+w(y,a)\\ \Longrightarrow f_x+w(x,b)&<f_y+w(y,b) \end{aligned} \] 证明很水： \[ \begin{aligned} f_x+w(x,a)+{\textcolor[rgb]{0.5,0.8,0.7}{w(x,b)+w(y,a)}}&<f_y+w(y,a)+\textcolor[rgb]{0.5,0.8,0.7}{w(x,a)+w(y,b)}\\ f_x+{\textcolor[rgb]{0.5,0.8,0.7}{w(x,b)}}&<f_y+\textcolor[rgb]{0.5,0.8,0.7}{w(y,b)}\\ \end{aligned} \] 绿色的的是四边形不等式。

至于如何实现四边形不等式呢？

给出以下代码：

void dp(int x,int l,int r,int tl,int tr){
    int mid=(l+r)>>1;
    int mn=1e18,pos=tr;
    for(int j=tl;j<=min(tr,mid-1);j++){
        if(mid-j>=w[x].size()) continue;
        int val=f[j]+w[x][mid-j];
        if(val<mn){
            mn=val,pos=j;
        }
    }
    if(l==r){
        g[l]=min(g[l],mn);return;
    }
    dp(x,l,mid,tl,pos);dp(x,mid+1,r,pos,tr);
}

涵义： dp(X,l,r,tl,tr) 是当前的状态在 l,r 这个范围，决策状态在 tl,tr 这个范围。

要记住了呀，这个含义是分治，而不是整体二分！。

这是 这个题 部分代码，需要注意的是我们仅仅保证了 \([1,\mathrm{lim}]\) 处的凸性，而未保证 \(0\) 的决策也具有单调性，所以 \(0\) 是一个特殊转移。

也就是为什么我们只能循环 j 到 mid-1.

---

半在线的话可以二分加队列。

实际上由于说的性质，对于点对 \((x,y),x<y\) 来说，如果 \(trans(x,p)\) 劣于 \(trans(y,p)\) 那么 \(i>p,trans(x,i)\) 将必不可能优于 \(trans(y,i)\) 。

说明了对于两个转移起点 \(x,y\) 存在这样的一个 \(p\)，使得 \(x\to \le p\) 优于 \(y\to \le p\)；而 \(\ge p\) 那边大小情况相反。

维护一个队列，\(l\) 端是先前最优决策，如果此时比 \(l+1\) 劣，直接弹出。

\(r\) 段是时间最后决策，如果 \(now\) 比 \(r\) 要更加优秀（相比 \(r-1\)），那就可以弹出 \(r\) 了。

比较优秀和劣都是二分出端点。

注意这个队列需要满足对于任意两个相邻的转移起点，上文提到的优劣分解点 \(p\) 需要单调递增。这也是为啥我们要pop back 的原因。

一种感觉是单调性是只属于转移起点的，而转移终点就没啥性质。

---

update at 2022.4.15

这里就大概总结一下 Max,+ 这种 dp 的常见优化技巧？

0. 决策单调性，四边形不等式，在 min 下记忆方法，包含大于交叉，交叉小于包含。也就是我们更期待交叉的值。
1. 斜率优化，将 \(\mathrm{dp}(n)=\max(\mathrm{dp}(i)+v_i+w_iw_n)\)，将 \(\mathrm{dp}(i)+v_i\) 看作 \(y\)，\(w_i\) 看作 \(x\) ，此时变成过 \((x,y)\) 斜率为 \(w_n\) 的直线截距问题，可以放到凸包上了。
2. 李超树。

---

再次upd at 2022-9-15 。

真心需要学一下蒙日矩阵了。