决策单调性学习笔记

· · 算法·理论

决策单调性：

对于形如

f_i=\min_{0\le j<i}\{f_j+w(j,i)\}

的状态转移方程，记p_i为使得f_i取到最小的j，那么p_i就是f_i的最优决策。

如果p_i在[1,N]上单调不减，那么称f具有决策单调性

void work() { int hh=0,tt=-1; for (int i=1;i<=n;i++) { while (hh<=tt && w(i,q[tt].l)>w(q[tt].j,q[tt].l)) tt--; if (hh>tt) q[++tt]={i,i,n}; else if (w(i,n)>w(q[tt].l,n)) { int l=q[tt].l,r=q[tt].r; int res; while (l<=r) { int mid=(l+r)>>1; if (w(q[tt].j,mid)>=w(i,mid)) { res=mid; l=mid+1; } else r=mid-1;
}
q[tt].r=res; q[++tt]={i,res+1,n}; } while (hh<=tt && q[hh].r<i) hh++; if (q[hh].l<i) q[hh].l=i; int j=q[hh].j; f[i]=max(f[i],w(j,i)); } }



  时间复杂度$O(n\log n)$

#### **四边形不等式**

**定义：** 

设$w(x,y)$是定义在$Z$上的二元函数，则如果对于定义域上的任意整数$a,b,c,d$满足$a\le b\le c \le d$，都有

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

那么称函数$w$满足四边形不等式

理解方式：交叉优于包含

- **定理：**

  设$w(x,y)$是定义在$Z$上的二元函数，则如果对于定义域上的任意整数$a,b$满足$a<b$，都有

  $w(a,b+1)+w(a+1,b)\ge w(a,b)+w(a+1,b+1)$

  那么函数$w$满足四边形不等式

- **定理：** 

  - 对于形如

    $f_i=\min_{0\le j<i}\{f_j+w(j,i)\}$

    的状态转移方程，如果$w(j,i)$满足四边形不等式，那么$f$具有决策单调性

  - 对于形如

    $f_{i,j}=\min_{i\le k < j}\{f_{i,k}+f_{k+1,j}+w(i,j)\}$

    的状态转移方程，如果以下两个条件成立：

    ①$w$满足四边形不等式

    ②对于任意的$a\le b \le c\le d$，有$w(a,d)\ge w(b,c)$

    那么$f$也满足四边形不等式

    记$p_{i,j}$为使得$f_{i,j}$取到最小的$k$，如果$f$满足四边形不等式，那么对于任意的$i<j$，都有$p_{i,j-1}\le p_{i,j} \le p_{i+1,j}$

---

### **例题：**

**原题：**

[P3515 [POI 2011] Lightning Conductor](https://www.luogu.com.cn/problem/P3515)

对于每个$i$求一个最小的非负整数$p$，使得$\forall j\in[1,n]$，都有：$a_j\le a_i+p-\sqrt{|i-j|}$

$n\le 5\times 10^5$

**正解：**

移项得到$p+a_i\ge a_j+\sqrt{|i-j|}$，即只需要对每个$a_i$求出$\max_{1\le j\le i}\{a_j+\sqrt{|i-j|}\}$
绝对值可以通过前后分别扫一遍去掉，于是化简掉得$\max_{1\le j\le i}\{a_j+\sqrt{i-j}\}$

定义$f_i=\max_{1\le j\le i}\{a_j+\sqrt{i-j}\}$，此时我们定义$w(j,i)=\sqrt{i-j}$

考虑$w(j,i)$是否满足四边形不等式，

对于$a<b$，

$$

w(a,b+1)+w(a+1,b)=\sqrt{a-b-1}+\sqrt{a-b+1} \\

w(a,b)+w(a+1,b+1)=\sqrt{a-b}+\sqrt{a-b}=2\sqrt{a-b} \\

\therefore w(a,b+1)+w(a+1,b)-[w(a,b)+w(a+1,b+1)]= \\

\sqrt{a-b-1}+\sqrt{a-b+1}-2\sqrt{a-b} \\

$$

$$
令T=a-b，原式= \\

\sqrt{T-1}+\sqrt{T+1}-2\sqrt{T} \\

=(\sqrt{T+1}-\sqrt{T})-(\sqrt{T}-\sqrt{T-1}) \\

由于函数f(x)=\sqrt{x+1}-\sqrt{x}单调递减， \\

\therefore \sqrt{T+1}-\sqrt{T}<\sqrt{T}-\sqrt{T-1}\\
\therefore 原式<0 \\

$$

所以有：

$$
w(a,b+1)+w(a+1,b)\le w(a,b)+w(a+1,b+1)
$$

由定理推广可以得到定义域内的任意整数$a\le b\le c\le d$

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

由于此题求的是$\max$，所以将四边形不等式决策单调性证明的符号反过来就可以得到此题中的$f$满足决策单调性

于是用队列/分治即可优化$DP$，$O(n\log n)$解决此题

---

**原题：**

[珠宝 /「NAIPC2016」Jewel Thief](https://loj.ac/p/6039)

$n$个物品，第$i$个重量为$c_i$，价值为$v_i$，求$1\sim k$大小的背包最大价值

$n\le 10^6,K\le 5\times 10^4,c_i\le 300$

**正解：**

定义$f_{c,i}$表示考虑$c_i\le c$的物品，大小为$i$的背包所能获得的最大价值

用$w(c,k)$表示$j$个重量为$c$的物品所能获得的最大价值

考虑体积固定为$i$，有状态转移方程：

$$

{\large f_{c,i}=\max_{0\le j \le \frac{i}{c}}\{f_{c-1,i-jc}+w(c,j)\}}

$$

可以看成：

$$
{\large f_{i}=\max_{0\le j \le \frac{i}{c}}\{g_{i-jc}+w(c,j)\}}
$$

考虑按照$i\bmod c$来分组，枚举$r$表示$i\bmod c=r$的组，那么$i=r+xc,i-jc=r+xc-jc=r+(x-j)c$，于是

$$
{\large f_{r+xc}=\max_{0\le j \le x}\{g_{r+(x-j)c}+w(c,j)\}}
$$

预处理出$pos_p=r+pc$，式子即可转化，看成

$$
{\large f_{pos_{x}}=\max_{0\le j \le x}\{g_{pos_{x-j}}+w^\prime(j)\}}
$$

即

$$
{\large f_{pos_{x}}=\max_{0\le j \le x}\{g_{pos_{j}}+w^\prime(x-j)\}} \\

{\large f_{pos_{x}}=\max_{0\le j \le x}\{g_{pos_{j}}+w^{\prime\prime}(x,j)\}}
$$

发现$w^{\prime\prime}$满足四边形不等式，于是有决策单调性，优化，做完了。

时间复杂度：$O(\sum_{c=1}^{m}m\frac{m}{c}\log \frac{m}{c})=O(m(\sum_{c=1}^{C}\log \frac{m}{c}))=O(Cm\log m)$

---

**原题：** [GYM105657L](https://codeforces.com/gym/105657/problem/L)

给定经验值序列 $a_i$ 和从 $i − 1$ 级升到 $i$ 级需要的经验 $b_i$，保证 $b_i \le b_{i+1}$。
将 $a_i$ 分段，每段的贡献为经验和能够升到的等级减 $c$，求最大贡献和。
$n, m, c \le 5 \times 10^5，
\sum a_i,\sum b_i \le 10^{12} $

**正解：**

定义$f_i$表示考虑$a$的前$i$个能够得到的最大贡献和

转移：$f_i=\max_{0\le j<i} \{ f_j+w(j,i) \}$

用$sa$表示$a$的前缀和数组，$sb$表示$b$的前缀和数组，用$pos(j,i)$表示用$sa_i-sa_j$能升到多少级，有

$pos(j,i)=\max\{ k\in Z | sb_k\le sa_i-sa_j \}$

$w(j,i)$表示用$sa_i-sa_j$能得到的最大贡献，有

$w(j,i)=pos(j,i)-c$

但是这个$w(j,i)$并不满足四边形不等式，考虑转化

定义
$$
sb_{ext}(x)=sb_{\lfloor x \rfloor}+\{x\}\times b_{x+1} \\
w_{ext}(j,i)=\max \{ k\in R | sb_{ext}(x)\le sa_i-sa_j\}-c \\
$$

有

$$
w_{ext}(j,i)=w(j,i)+\frac{(sa_i-sa_j-sb_{pos(j,i)})}{b_{pos(j,i)+1}}
$$

发现$w_{ext}(j,i)$在实数域满足四边形不等式

由这些可以证明任意$a<b<c<d$都有$w(a,c)+w(b,d)+1\ge w(a,d)+w(b,c)$

所以有$w(a,c)-w(b,c)+1\ge w(a,d)-w(b,d)$

两边同时加上$f_a-f_b$，
$(f_a+w(a,c))-(f_b+w(b,c))+1\ge (f_a+w(a,d))-(f_b+w(b,d))$

那么此时如果$f_a+w(a,c)<f_b+w(b,c)$，那么$(f_a+w(a,d))-(f_b+w(b,d))\le 0$，即

$f_a+w(a,d)\le f_b+w(b,d)$

也就是说，对于$c$严格更优的决策对于以后的$d$而言一定不会更劣，有了决策单调性，考虑使用队列优化，此时发现决策的值相等时无法确定到底用哪个决策更优，不满足完全单调性，于是此时可以使用$w_{ext}(j,i)$代替$w(j,i)$进行决策，由于$w_{ext}(j,i)$满足四边形不等式，有完全单调性，所以可以做。