决策单调性 笔记

一、基本概念

1. 一些术语

$f_i=\underset{1\le j<i}{min}(f_j+w(j+1,i))$。

• 这是一个最小化问题 $i$；
• 它的决策集合是 $\{j\mid 1\le j<i\}$；
• 最优决策点 $\mathrm{opt}(i)=\arg \underset{1\le j<i}{min}(f_j+w(j+1,i))$，即取到最小值时 $j$ 的位置。

2. 四边形不等式

若 $a\le b\le c\le d$，满足：

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

则称 $w$ 满足四边形不等式（交叉小于包含）。

四边形不等式成立的一个充要条件：

$$\mathrm{\forall }a<b,w(a,b)+w(a+1,b+1)\le w(a,b+1)+w(b,a+1)$$

对于最大化问题，应将 $\le$ 变为 $\ge$。

3. 区间单调性

若 $a\le b\le c\le d$，满足：

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

则称 $w$ 满足区间单调性。

4. 决策单调性

设对于一个最大/最小化问题 $i$，它的最小可行解是 $\mathrm{opt}(i)$。

若对于 $i_1\le i_2$，满足：

$$\mathrm{opt}(i_1)\le \mathrm{opt}(i_2)$$

则称具有决策单调性。

二、常见形式

1. 1D

(1). 分治类问题

$$f_i=\underset{1\le j\le i}{min}w(j,i)$$

一般而言，$w(j,i)$ 是 $O(1)$ 可求的。

定理一

若 $w$ 满足四边形不等式，则 $f$ 满足决策单调性。

证明：反证法。假设对于 $a<b\le c<d,\mathrm{opt}(c)=b,\mathrm{opt}(d)=a$，则根据定义 $w(a,d)\le w(b,d)$ 且 $w(b,c)<w(a,c)$，移项可得 $w(a,d)-w(b,d)\le 0<w(a,c)-w(b,c)$，即 $w(a,d)+w(b,c)<w(a,c)+w(b,d)$，与“$w$ 满足四边形不等式”矛盾。故假设不成立，定理成立。

假设 $l,r$ 是待处理区间的左边界，$i$ 是当前正在处理的问题（$i=\lfloor \frac{l+r}{2}\rfloor$），$kl$，$kr$ 是可能出现答案的答案的左边界和右边界。

通过暴力枚举 $kl$ 到 $kr$，求出 $i$ 的最优决策 $k$，由于问题 $w$ 具有决策单调性，所以，对于 $[l,i-1]$ 这一段区间，答案的范围是 $[kl,k]$；对于 $[i+1,r]$ 这一段区间，答案的范围是 $[k,kr]$。递归分治即可，时间复杂度为 $O(n\log n)$。

void work(int l, int r, int kl, int kr) {
	if (l > r) return;
	int i = l + r >> 1, k = kl;
	for (int j = kl; j <= kr; j++)
		if (w(j, i) > w(k, i)) k = j;
	p[i] = max(p[i], w(k, i));
	work(l, i - 1, kl, k);
	work(i + 1, r, k, kr);
}

(2). 二分队列类问题

$$f_i=\underset{1\le j<i}{min}(f_j+w(j+1,i))$$

需要用二分队列的四边形不等式优化，有一个鲜明的特征：$i$ 的决策依赖于以前的决策。

根据决策单调性，可以知道每一个决策一定都是一段连续区间问题的最优决策点。

因此，设 $l{t}_i$，$r{t}_i$ 表示 $[l{t}_i,r{t}_i]$ 范围内的问题的决策是 $i$。

一开始，一个问题都还没处理，$l{t}_0=1,r{t}_0=n$。

定义一个单调队列，队列头表示问题 $i$ 的最优决策。

开始处理第 $i$ 个问题：

1. $f_i=w(q_{\mathrm{front}},i)$，处理 $f_i$。

2. 根据决策单调性，如果对于 $l{t}_{q_{\mathrm{back}}}$ 这个问题，当前的 $i$ 决策还比以往的 $q_{\mathrm{back}}$ 决策要优，那么 $q_{\mathrm{back}}$ 决策不再可能成为最优决策，队尾可以弹出了。

3. 将所有在第二步中“整个区间都被弹出”的决策清理掉后，此时队尾的决策对应的问题区间，它的右半部分很有可能也是决策 $i$ 更优，因此二分在最后的这个问题区间，决策 $i$ 更优的分界点是哪里，将分界点的左边的问题归给原本队尾的决策。

4. 如果分界点还没有到达 $n$，那么就添加一个 $i$ 决策最优的 $[\mathrm{右}\mathrm{边}\mathrm{界},n]$ 的问题区间。

5. 最后，如果 $q_{\mathrm{front}}$ 这一个决策的问题区间右边界就是 $i$，那么这个决策后面就没用了，从队头弹出。

void work() {
    deque<int> q;
    q.push_back(0);
    lt[0] = 1, rt[0] = n;
    for (int i = 1; i <= n; i++) {
        f[i] = w(q.front(), i);
        while (i < lt[q.back()] and w(i, lt[q.back()]) < w(q.back(), lt[q.back()])) q.pop_back();
        int l = max(i, lt[q.back()] - 1), r = rt[q.back()] + 1;
        while (l + 1 < r) {
            int mid = l + r >> 1;
            if (w(i, mid) < w(q.back(), mid)) r = mid;
            else l = mid;
        }
        rt[q.back()] = r - 1;
        if (r <= n) {
            q.push_back(i);
            lt[i] = r, rt[i] = n;
        }
        while (i == rt[q.front()]) q.pop_front();
    }
}

2. 2D

(1). 区间分拆问题

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

令 $g_j=f_{i-1,j}$，变为 1D 问题。

(2). 区间合并问题

石子合并问题。

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

定理二

若 $w$ 满足四边形不等式，则 $f$ 满足决策单调性。

证明：当 $i=j$ 时，定理成立。当 $i+1=j$ 时，原式相当于对若干个四边形不等式求和再取最小值，仍满足四边形不等式。以此类推，可以得到 $f_{i,j}$ 满足四边形不等式和决策单调性。

定理三

有 $\mathrm{opt}(i-1,j)\le \mathrm{opt}(i,j)\le \mathrm{opt}(i,j+1)$。

证明：第二个小于等于号是 1D 情况。对于第一个小于等于号考虑反证法。设 $x=\mathrm{opt}(i-1,j),y=\mathrm{opt}(i,j)$，且 $x>y$。则有 $i\le y<x<j$。可以得到 $f_{i-1,x}+f_{x+1,j}\le f_{i-1,y}+f_{y+1,j}$，$f_{i,y}+f_{y+1,j}\le f_{i,x}+f_{x+1,j}$。两式相加得 $f_{i-1,x}+f_{i,y}\le f_{i-1,y}+f_{i,x}$，与 $f$ 是四边形不等式矛盾。故 $x<y$。

三、刷题总结

真理（并非

事实上，考场上遇到了像是四边形不等式的题，我更愿意写个暴力判断是否满足，但是平时练习还是很需要证明的。

1. P3515 [POI2011] Lightning Conductor / SP9070 LIGHTIN - Lightning Conductor

求：

$$p_i=\underset{j=1}{\overset{n}{max}}\{a_j+\sqrt{|i-j|}\}-a_i$$

先简单处理一下：

$$p_i=max(\underset{j=1}{\overset{i}{max}}\{a_j+\sqrt{i-j}\},\underset{j=i}{\overset{n}{max}}\{a_j+\sqrt{j-i}\})-a_i$$

只要处理出其中一个 $max$，另一个就可以用同样的方法解决。

设 $w(j,i)$ 表示 $a_j+\sqrt{i-j}$，则原式变为

$$p_i=\underset{j=1}{\overset{i}{max}}w(j,i)-a_i$$

这是一个最大化问题，接着证明 $w$ 满足四边形不等式。

设 $i<j$，则

• $w(i,j)+w(i+1,j+1)=a_i+a_{i+1}+2\sqrt{j-i}$；
• $w(i,j+1)+w(i+1,j)=a_i+a_{i+1}+\sqrt{j-i+1}+\sqrt{j-i-1}$。

令 $x=j-i\ge 1$，$w$ 满足四边形不等式的充要条件是 $2\sqrt{x}\ge \sqrt{x+1}+\sqrt{x-1}$。

两边同时平方并移项，得 $2x\ge 2\sqrt{x+1}\sqrt{x-1}$。

再次两边同时平方，得 $4x^2\ge 4x^2-4$，恒成立，故 $w$ 满足四边形不等式。

分治求即可。

2. P3195 [HNOI2008] 玩具装箱

求：

$$f_i=\underset{j=1}{\overset{i}{min}}\{f_j+(x-L{)}^2\}$$

（$x=i-(j+1)+\sum _{k=j}^i{c}_k$，$c,L$ 已给出。

$i$ 的决策依赖 $i$ 以前的问题的决策，故使用二分队列法。

3. P4767 [IOI 2000] 邮局 加强版

2D 板子。