四边形不等式
基本概述
四边形不等式本质是在决策时利用单调性进行的一种优化，通常与动态规划结合
例题 石子合并
我们先看一道非常经典的问题：
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出1个算法,计算出将N堆石子合并成1堆最小得分.
暴力做法
显然是经典区间DP
断环为链后，令 $dp[i][j]$ 表示区间答案，则
$dp(l,r) = \min\limits_{l \le k \textless r}(dp(l,k))+dp(k+1, r)))+w(l, r)) $
显然，这样直接做的话有n2个状态，每个状态的迭代需要O(n)枚举，所以复杂度是O(n3)，为了方便之后的对比，我们直接写出暴力代码代码如下：
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 \textless 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$。一个排版方案中每行相邻两个句子之间的空格也算在这行的长度中（可参见样例中第二组数据）。每行末尾没有空格。
数据规模与约定
| 测试点 | $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$ 。
标签：10,le,不等式,修正,leq,四边形,dp From： https://www.cnblogs.com/Assassins-Creed/p/17300030.html