四边形不等式

基本概述

四边形不等式本质是在决策时利用单调性进行的一种优化，通常与动态规划结合

例题 石子合并

我们先看一道非常经典的问题：

在一个园形操场的四周摆放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：如何保证w(i,j)符合四边形不等式呢？可以将最小值换成最大值来做吗？

假设f是最小值

首先要证 \(f[i][j]+f[i+1][j+1]<=f[i+1][j]+f[i][j+1]\) (就是四边形不等式

右边的\(f[i+1][j]\)和\(f[i][j+1]\)都有断点，就是最优的一个切断位置

假设\(f[i+1][j]\)的最优断点k=x，\(f[i][j+1]\)的最优断点k=y

然后式子转化成\(f[i][j]+f[i+1][j+1]<=f[i+1][x]+f[x+1][j]+sum[i+1][j]+f[i][y]+f[y+1][j+1]+sum[i][j+1]\)

但是对于\(f[i][j]\)，最优的切断位置不一定是x

所以有\(f[i][j]<=f[i][x]+f[x+1][j]+sum[i][j]\)，也就是\(f[i][j]\)一定是最小的

同理\(f[i+1][j+1]<=f[i+1][y]+f[y+1][j+1]+sum[i+1][j+1]\)

然后sum是满足单调性和四边形不等式的，也就是\(sum[i][j]+sum[i+1][j+1]==sum[i][j+1]+sum[i+1][j]\)

得证

那么万一f是最大值，符合四边形不等式吗？

答案是不符合的，由于大小值的关系，原来的<=变成了>=，于是\(f[i][j]>=f[i][x]+f[x+1][j]+sum[i][j]\)，这样一来就导致f是左大右小，sum还是左小右大，这下比不了了，于是不可如此优化。

当然，最大值的情况下其实有更简单的办法，由于对于\(f[i][j]\)来说，\(f[i+1][j-1]\)这个子状态是固定的，所以只要考虑两端即可，即\(f[i][j] = max(f[i+1][j], f[i][j-1])\)

网上有个更清晰的说明：

首先可以把最后一步看成两堆石子合并，倒数第二部看成三堆石子中的两堆合并，再与第三堆合并
那三堆中哪两堆合并呢？
(用w[i]表示第i堆重量)
前两堆:\(w1=2w[1]+2w[2]+w[3]\)
后两堆:\(w2=w[1]+2w[2]+2w[3]\)
所以应该将1号和3号中较大的一堆与第2堆合并，也就是把一堆合并得尽可能大，也就是只考虑两端，因为中间的状态对于\(w(1,3)\)来说是一样的

其实根据大佬的经验，判断是否符合性质最稳妥的办法是：打表

往往就是考场上发现DP式写出来后有点像四边形不等式的优化，就去猜这个结论，然后打个表看看是否符合...

因为\(w(i,j)\)这个二维函数是否符合这中单调性是取决于题目的，无法进行特定的总结，这里的石子合并这道题，得出结论是显然的，但是更复杂的情况呢？

一个确定的但是其实没啥用的辅助条件是：当w(i,j)为凸函数时，即符合四边形不等式，也就是当且仅当对于任意 \(i<=j\) 有 \(w(i,j)+ w(i+1,j+1)<= w(i+1,j)+ w(i,j+1)\)（具体减1还是加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)\)

对 \(s[i,j-1] \leq s[i,j] \leq s[i+1,j]\) 的证明：

设 \(m_k[i,j]=m[i,k]+m[k,j]\)，\(s[i,j]=d\)

对于任意 \(k<d\)，有 \(m_k[i,j] \geq m_d[i,j]\)（这里以 \(m[i,j]=\min{m[i,k]+m[k,j]}\) 为例，\(\max\) 的类似），那么只有当 \(s[i+1,j] \geq s[i,j]\) 时才有可能有 \(m_k[i+1,j] \geq m_d[i+1,j]\)，反之亦然，接下来只要证明 \(m_k[i+1,j] \geq m_d[i+1,j]\)，

\((m_k[i+1,j]-m_d[i+1,j])-(m_k[i,j]-m_d[i,j])\)

\(=(m_k[i+1,j]+m_d[i,j])-(m_d[i+1,j]+m_k[i,j])\)

\(=(m[i+1,k]+m[k,j]+m[i,d]+m[d,j])-(m[i+1,d]+m[d,j]+m[i,k]+m[k,j])\)

\(=(m[i+1,k]+m[i,d])-(m[i+1,d]+m[i,k])\)

\(\because m\) 满足四边形不等式

\(\therefore\) 对于 \(i<i+1 \leq k<d\) 有 \(m[i+1,k]+m[i,d] \geq m[i+1,d]+m[i,k]\)

\(\therefore (m_k[i+1,j]-m_d[i+1,j]) \geq (m_k[i,j]-m_d[i,j]) \geq 0\)（应用四边形不等式）

\(\therefore s[i,j] \leq s[i+1,j]\)，同理可证 \(s[i,j-1] \leq s[i,j]\)

证毕

例题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 optimal solution is : {1, 2, 3} | {4, 5, 6} | {7, 8}.

显然，可以根据划分型DP的套路搞出公式：\(dp[k][i]=\min\limits_{l\le k\lt r}(dp[l][k]+dp[k+1][r]) + w(l,r)\)

w(l,r)其实就是个二维前缀和，打个表发现符合四边形不等式...（其实前缀和必定符合这个性质）

于是...

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\)。一个排版方案中每行相邻两个句子之间的空格也算在这行的长度中（可参见样例中第二组数据）。每行末尾没有空格。

数据规模与约定

所有句子的长度不超过 \(30\) 。

本栏目推荐文章
• dp优化-决策单调性 / 四边形不等式
• 基本不等式
• 六边形战士与六边形架构：强大能力的双重赋能
• 什么是多边形网格以及如何编辑它？
• (弱化版) Marcinkiewicz–Zygmund 不等式
• 240104 杂题全谈 四边形不等式
• 常用不等式
• 六边形架构
• uniapp map地图 多边形中心点
• 什么是多边形网格以及如何编辑它？

四边形 不等式 四边四边形 不等式 四边 四边形 不等式 四边 笔记 四边形 不等式 四边 诗人 四边形 不等式 四边240104 四边形 不等式 四边 讲稿 四边形 不等式 四边 邮局 不等式 四边 千丝万缕 随感 四边形 四边 四边形 四边 三角形 几何