四边形不等式
concert_B
·
·
科技·工程
四边形不等式
基本概述
四边形不等式本质是在决策时利用单调性进行的一种优化，通常与动态规划结合
例题 石子合并
我们先看一道非常经典的问题：
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出1个算法,计算出将N堆石子合并成1堆最小得分.
暴力做法
显然是经典区间DP
断环为链后，令 dp[i][j] 表示区间答案，则
dp(l,r) = \min\limits_{l \le k \le r}(dp(l,k))+dp(k+1, r)))+w(l, r))
显然，这样直接做的话有n^2个状态，每个状态的迭代需要O(n)枚举，所以复杂度是O(n^3)，为了方便之后的对比，我们直接写出暴力代码代码如下：
for(int i=n*2-1;i;i--){
for(int j=i+1;j<n*2;j++){
for(int k = i; k < j; k++)
if(f[i][k]+f[k+1][j]+sum[j]-sum[i-1]<f[i][j]){
f[i][j] = f[i][k]+f[k+1][j]+sum[j]-sum[i-1];
}
}
}
四边形不等式初探——先走一遍过程
关于这个问题的优化，便是典型的四边形不等式
我们从问题解决的角度来学习，干脆先走一遍过程，中间的证明环节我们先不管他
对于序列上的四个点l、l'、r'、r，如果满足以下两个性质☆挖坑1☆：
①区间覆盖的单调性：若l \leq l' \leq r' \leq r，则w(i', j')<w(i,j)
一般来说，这个性质一眼能看出来，且大多情况都是可以满足的，所以一般教程提到似乎不多
②四边形不等式：若l \leq l' \leq r' \leq r，则w(l,r')+w(l',r) \leq w(l',r')+w(l,r)
我们可以把4个区间看成两条线段的端点，也就是线段相交的情况比包含的情况更优，就像是一个四边形的对角线和上下边进行对比，估计这个名字也是由此而来的
在看我们的公式：dp(l,r) = \min\limits_{l \le k \le r}(dp(l,k))+dp(k+1, r)))+w(l, r))
只要w(l,r)满足该性质，则有两个神奇的结论：
①dp(l,r)同样满足四边形不等式
②若dp(l,r)的最优决策点为m，则m介于dp(l,r-1)和dp(l+1,r)的最优决策点之间
即m(l,r-1) \leq m(l,r) \leq m(l+1,r)
这里还是放到矩阵上图形化理解会快一点
关键在于第二个结论，因为这个结论直接影响了代码中k这一层的循环范围！
原理先放着☆挖坑2☆
我们完善代码：
for(int i = 1; i < 2*n; i++)
m[i][i] = i;//初始化
for(int i=n*2-1;i;i--){
for(int j=i+1;j<n*2;j++){
for(int k = m[i][j-1]; k < m[i+1][j]+1; k++)
if(f[i][k]+f[k+1][j]+sum[j]-sum[i-1]>f[i][j]){
f[i][j] = f[i][k]+f[k+1][j]+sum[j]-sum[i-1];
m[i][j] = k; //记录决策点
}
}
}
至此，代码得到优化，虽然看着还是三层循环，但是本质是O(n^2)的，从图形上看，每层循环的新状态是在迭代矩阵上的一条斜线，以第一层主对角线为例，斜线的循环总次数是m(2,1)-m(1,0)+m(3,2)-m(2,1)……+m(i+1,j)-m(i,j-1) +……+ m(n+1,n)-m(n,n-1)（加1减1的细节去掉了反正不影响），会发现全部抵消，所以宏观上均摊是O(n^2)的
至此问题解决
证明过程
流程简单，但是为什么可以这么推呢？
挖坑1：如何保证dp(i,j)符合四边形不等式呢？可以将最小值换成最大值来做吗？
根据不同情况下的证明分类
我们对 l \le l' \le r' \le r 的情况进行分类讨论和证明。
情况一：当 l' = l
当 l' = l 时，有以下证明过程：
又因为 $l = l'$，所以：
$dp(l',r') + dp(l,r) = dp(l,r') + dp(l,r)$。
由此可得命题 成立，证明完成。
情况二：当 $r' = r
与 l' = l 的情况类似，不再赘述。
情况三：当 l' = r'
根据 dp 方程定义，当 l' = r' 时，dp(l',r')=0，因此：
从而进一步得出 $dp(l,r) = dp(l,r) + dp(l',r')$，命题 成立，证明完成。
情况四：当 $l' = r' \le k$，其中 $k = opt(l,r)
此时我们结合数学归纳法来证明。
-
第一步：证明当 r = r' 时， 成立。此已在 r' = r 的情形中证明。
-
第二步：设当 r \ge r' 时 成立，则可推导出 P(\{x|x>r\}) 成立。由于 r' \le k < r，可将第二步转化为：假设 P(k) 成立，可推导出 成立。
也就是说我们有如下假设：
在此假设条件下，我们可以证明：
$dp(l,r') + dp(l',r) \le dp(l,r') + dp(l',k) + dp(k+1,r) + c(l',r)
$\le dp(l,k) + dp(l',r') + dp(k+1,r) + c(l,r)$ （根据假设）
$= dp(l,k) + 0 + dp(k+1,r) + c(l,r)$ （根据 $dp$ 定义）
$= dp(l,r)$ （根据公式(1)）
$= dp(l,r) + dp(l',r')$ （根据公式(2)）
证明完毕。
当 $k < l' = r'
同上面的方法，利用数据归纳法（这里将命题参数从 r 换成 l，即命题 P(l)）进行证明。
-
第一步：证明当 l = l' 时，P(l) 成立，此在 l' = l 的情况中已证明。
-
第二步：设当 l \le l' 时 P(l) 成立，则可推导出 P(\{x|x<l\}) 成立。由于 l \le k < l'，因此可将第二步转化为：假设 P(k+1) 成立，可推导出 P(l) 成立。
有如下假设：
在此假设下，有：
$dp(l,r') + dp(l',r) \le c(l,r') + dp(l,k) + dp(k+1,r') + dp(l',r)
$\le c(l,r) + dp(l,k) + dp(k+1,r) + dp(l',r')$ （根据假设）
$\le c(l,r) + dp(l,k) + dp(k+1,r) + 0$ （根据 $dp$ 定义）
$= dp(l,r)$ （根据公式(1)）
$= dp(l,r) + dp(l',r')$ （根据公式(2)）
证明完毕。
当 l < l' < r' < r
设 $x = opt(l,r)$，$y = opt(l',r')$。
由 $opt$ 定义可得：$l \le x < r$, $l' \le y < r'$。
情形一：$y < x
此时有 l < l' \le y < r', x < r。于是 l \le y < r', l' < x < r。根据推论(1)可得：
dp(l,r') \le dp(l,y) + dp(y+1,r') + c(l,r')
利用数据归纳法证明命题 $P(r')$。
1. 当 $r' = l'$ 时，$P(r')$ 成立，此在 $l' = r'$ 时已证明。
2. 假设当 $r' \ge l'$ 时 $P(r')$ 成立，可推出 $P(\{x|x>r'\})$ 成立。由于 $r' > y \ge l'$，可将第二步转化为：假设 $P(y)$ 成立，则可推出 $P(r')$ 成立。而因为 $x > y$，有如下假设：
$dp(l,y) + dp(l',x) \le dp(l',y) + dp(l,x)$。
在此假设下，可证明：
$dp(l,r') + dp(l',r) \le dp(l,y) + dp(y+1,r') + c(l,r') + dp(l',x) + dp(x+1,r) + c(l',r)
$\le dp(l',y) + dp(y+1,r') + c(l',r') + dp(l,x) + dp(x+1,r) + c(l,r)$ （根据假设）
$= dp(l',r') + dp(l,r)$ （根据公式(1)）
证明完毕。
情形二：$x \le y
有 l \le x, l' \le y < r' < r，故 l \le x < r', l' \le y < r。根据推论(1)可得：
dp(l,r') \le dp(l,x) + dp(x+1,r') + c(l,r')
又有 $x+1 \le y+1 < r' < r$，通过数据归纳法我们有如下假设：
$dp(x+1,r') + dp(y+1,r) \le dp(x+1,r) + dp(y+1,r')$。
在此假设下，可证明：
$dp(l,r') + dp(l',r) \le dp(l,x) + dp(x+1,r') + c(l,r') + dp(l',y) + dp(y+1,r) + c(l',r)
$\le dp(l,x) + dp(x+1,r) + c(l,r) + dp(l',y) + dp(y+1,r') + c(l',r')$ （根据假设）
$= dp(l,r) + dp(l',r')$ （根据公式(1)）
证明完毕。
##### 挖坑2：为什么只要w(l,r)满足四边形不等式，就可以推导出结论：若dp(l,r)的最优决策点为m，则m介于dp(l,r-1)和dp(l+1,r)的最优决策点之间，即$m(l,r-1) \leq m(l,r) \leq m(l+1,r)
若 dp 满足四边形不等式，则 m 满足单调性，即\
m(l,r-1) \le m(l,r) \le m(l+1,r)
证明
设 x = m(l,r-1), y = m(l,r), z = m(l+1,r)，\
有以下不等式：\
l \le x < r-1$, $l \le y < r$, $l+1 \le z < r
我们用反证法证明：
-
若 y < x，结合上述不等式可得\
y+1 < x+1 \le r-1 < r
根据四边形不等式，可得：
dp(y+1,r-1)+dp(x+1,r)\le dp(y+1,r)+dp(x+1,r-1)
又因 y 是 dp(l,r) 的最佳决策点，即：
dp(l,y)+dp(y+1,r)\le dp(l,x)+dp(x+1,r)
将两式相加，消去相同项，可得：
dp(l,y)+dp(y+1,r-1)\le dp(l,x)+dp(x+1,r-1)
这个不等式意味着对于 dp(l,r-1) 来说，y 比 x 更佳，与前置条件 x 是 dp(l,r-1) 的最佳决策点矛盾。
因此，x > y 不成立，所以 x \le y，即 m(l,r-1) \le m(l,r)。
-
若 z < y，结合上述不等式可得：
l < l+1 \le z < y
根据四边形不等式，可得：
dp(l,z)+dp(l+1,y)\le dp(l,y)+dp(l+1,z)
又因 z 是 dp(l+1,r) 的最佳决策点，即：
dp(l+1,z)+dp(z+1,r)\le dp(l+1,y)+dp(y+1,r)
将两式相加，消去相同项，可得：
dp(l,z)+dp(z+1,r)\le dp(l,y)+dp(y+1,r)
这个不等式意味着对于 dp(l,r) 来说，z 比 y 更佳，与前置条件 y 是 dp(l,r) 的最佳决策点矛盾。
因此，y > z 不成立，所以 y \le z，即 m(l,r) \le m(l+1,r)。
综上所述，我们有：
m(l,r-1) \le m(l,r) \le m(l+1,r)m(l,r-1) \le m(l,r) \le m(l+1,r)
证毕
例题1：CF321E
Ciel and Gondolas
题面翻译
Ciel狐狸在游乐园里排队等待上摩天轮。现在有n 个人在队列里，有k 条船，第i条船到时，前q_{i} 个人可以上船。最后一条船将载走剩下的所有人，则q_{k} 此时载走的人数。
人总是不愿意和陌生人上同一条船的，当第i 个人与第j 个人处于同一条船上时，会产生u_{i,j} 的沮丧值。请你求出最小的沮丧值和。
一条船上的人两两都会产生沮丧值。
输入格式：
第一行两个数代表n ,k ，接下来n 行每行n 个数，第i 行第j 个数表示u_{i,j} 。
请使用快速读入的技巧，防止读入导致的TLE。
输出格式：
一行一个整数表示最小沮丧值。
贡献者：MSF_Akatsuki
样例 #1
样例输入 #1
5 2
0 0 1 1 1
0 0 1 1 1
1 1 0 0 0
1 1 0 0 0
1 1 0 0 0
样例输出 #1
0
样例 #2
样例输入 #2
8 3
0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1
1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 0
样例输出 #2
7
样例 #3
样例输入 #3
3 2
0 2 0
2 0 3
0 3 0
样例输出 #3
2
提示
In the first example, we can allocate people like this: {1, 2} goes into a gondolas, {3, 4, 5} goes into another gondolas.
In the second example, an mimal solution is : {1, 2, 3} | {4, 5, 6} | {7, 8}.
显然，可以根据划分型DP的套路搞出公式：dp[i][j]=\min\limits_{1\le k\lt j}(dp[i-1][k]) + w(k,j)
于是...
```cpp
dp[0][0] = 0;
for (int i = 1; i <= K; i++)
for (int j = N; j >= 1; j--){
for (int k = m[i - 1][j]; k <= m[i][j + 1]; k++)
if (dp[i][j] > dp[i - 1][k - 1] + cal(k, j)){
dp[i][j] = dp[i - 1][k - 1] + cal(k, j);
m[i][j] = k;
}
}
```
记得快读
#### 例2. \[NOI2009] 诗人小G
## 题目描述
小 G 是一个出色的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是诗的排版问题。
一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小 G 给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小 G 不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小 G 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的 $P$ 次方，而一个排版的不协调度为所有行不协调度的总和。
小 G 最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他。
## 输入格式
输入文件中的第一行为一个整数 $T$，表示诗的数量。
接下来为 $T$ 首诗，这里一首诗即为一组测试数据。每组测试数据中的第一行为三个由空格分隔的正整数 $N,L,P$，其中：$N$ 表示这首诗句子的数目，$L$ 表示这首诗的行标准长度，$P$ 的含义见问题描述。
从第二行开始，每行为一个句子，句子由英文字母、数字、标点符号等符号组成（ASCII 码 $33 \sim 127$，但不包含 `-`）。
## 输出格式
于每组测试数据，若最小的不协调度不超过 $10^{18}$，则第一行为一个数，表示不协调度。接下来若干行，表示你排版之后的诗。注意：在同一行的相邻两个句子之间需要用一个空格分开。
如果有多个可行解，它们的不协调度都是最小值，则输出任意一个解均可。若最小的不协调度超过 $10^{18}$，则输出 `Too hard to arrange`。每组测试数据结束后输出 `--------------------`，共 20 个 `-`，`-` 的 ASCII 码为 45，请勿输出多余的空行或者空格。
## 样例 #1
### 样例输入 #1
4
4 9 3
brysj,
hhrhl.
yqqlm,
gsycl.
4 9 2
brysj,
hhrhl.
yqqlm,
gsycl.
1 1005 6
poet
1 1004 6
poet
### 样例输出 #1
108
brysj,
hhrhl.
yqqlm,
gsycl.
--------------------
32
brysj, hhrhl.
yqqlm, gsycl.
--------------------
Too hard to arrange
--------------------
1000000000000000000
poet
--------------------
## 提示
#### 样例输入输出 1 解释
前两组输入数据中每行的实际长度均为 $6$，后两组输入数据每行的实际长度均为 $4$。一个排版方案中每行相邻两个句子之间的空格也算在这行的长度中（可参见样例中第二组数据）。每行末尾没有空格。
#### 数据规模与约定
| 测试点 | $T$ | $N$ | $L$ | $P$ |
| ---- | -------- | ------------------ | ------------------ | ------- |
| $1$ | $\le 10$ | $\le18$ | $\le 100$ | $\le5$ |
| $2$ | $\le 10$ | $\le 2\times 10^3$ | $\le 6\times 10^4$ | $\le10$ |
| $3$ | $\le 10$ | $\le 2\times 10^3$ | $\le 6\times 10^4$ | $\le10$ |
| $4$ | $\le 5$ | $\le 10^5$ | $\le 200$ | $\le10$ |
| $5$ | $\le 5$ | $\le 10^5$ | $\le 200$ | $\le10$ |
| $6$ | $\le 5$ | $\le 10^5$ | $\le 3\times 10^6$ | $2$ |
| $7$ | $\le 5$ | $\le 10^5$ | $\le 3\times 10^6$ | $2$ |
| $8$ | $\le 5$ | $\le 10^5$ | $\le 3\times 10^6$ | $\le10$ |
| $9$ | $\le 5$ | $\le 10^5$ | $\le 3\times 10^6$ | $\le10$ |
| $10$ | $\le 5$ | $\le 10^5$ | $\le 3\times 10^6$ | $\le10$ |
所有句子的长度不超过 $30$ 。
显然，有划分型DP，令$f[i]$表示前$i$个单词的最有不协调度：$f[i] = min(f[j]) + w(i,j)$，其中$w(i,j)$为$i$到$j$统一划分的不协调值，可用前缀和直接求得，注意空格的细节
但是$O(n^2)
令P[i]为f[i]的最优划分点，根据之前的性质，P[i]具有单调性，更强的一个性质就是：对于i<i'，必有P[i] \le P[i']，如此每次枚举的区间似乎由[1,i-1]变成了[p[i-1], i-1]，但这种优化其实没啥用，因为复杂度并没有改变，并没有之前二维的情况那样减少复杂度。
但是我们仍旧可以得到一个O(nlogn)的做法。
首先，对于最终状态，所有的P[i]是单调的，例如这样：
1 1 2 2 2 3 3 3 3 5 5 5 5 5 6 6 6
这样一来，我们转变一下思路，当枚举到i的时候，先更新出f[i]（怎么更新我们待会说），然后考虑当前的i这个位置作为最优断点的话能够影响到多少位置。
还是上面的例子，假设现在已经枚举到i=7了，所以前面所有的f[1]到f[6]都已经搞定了，整个P数组的状态就是之前的例子：
1 1 2 2 2 3 3 3 3 5 5 5 5 5 6 6 6
现在，我们处理f[7]，显然，目前第7个位置的最优断点为3，即P[7]=3，所以可以用公式f[7]=f[3]+w(4,7)计算出f[7]
接下来，我们考虑7这个位置作为最优断点的话能够影响到多少位置，我们这里要倒着考虑，先考虑最后一段的最左端位置15，最优断点为6，代入公式计算出的最优值为f[15]=f[6]+(7,15)，同样的，我们将7也作为断点带入，f[15]=f[7]+(8,15)，若后者更优，则说明这一整段都要替换为7（单调性嘛），而且还要照此思路往前循环，比对每一段的左端点。若前者更优，则说明这一段有可能只有后一半会被7替换，如：
1 1 2 2 2 3 3 3 3 5 5 5 5 5 6 7 7
这里我们可以考虑二分找到这个临界点，在这一段内二分一个位置mid，比较一下两个不同的f[mid]，即f[6][mid]+w(7,mid)和f[7][mid]+w(8,mid)即可。
具体实现方法不一，常见的是用一个双端队列存储每一段P值，队列元素是个三元组，(x,l,r)表示l到r这一段全部是x，一开始全部是0或者1也就是(0,1,n)或(1,1,n)，然后进行更新，每次枚举到i，先删队首，将区间不包含i的删去，如此则队首必然能得到当前f[i]的最优断点，然后队尾照着上面步骤删除，直至出现队伍中元素更优的情况，然后二分，二分之后删去原队尾(6 6 6)，添加两个新队尾(6)、(7 7)。
细节蛮多的，祝好运