算法竞赛专题解析│四边形不等式优化( 四 ) ：算法竞赛专题解析│四边形

w(i,j)+w(i′,j′)≥w(i′,j)+w(i,j′)i≤i′≤j≤j′
定义：
c(i,j)=w(i,j)+max(a(i,k)+b(k,j))i≤k≤j
引理3：若w、a、b都满足反四边形不等式，那么ccc也满足反四边形不等式。
引理4：如果a和b满足反四边形不等式，那么：
Kc(i,j)≤Kc(i,j+1)≤Kc(i+1,j+1)
i≤j
证明与引理1和引理2的证明类似。
07
一维决策单调性优化
上述的四边形不等式优化，是“二维决策单调性”优化。在“一维决策单调性”的情况下也能优化。
李煜东《算法竞赛进阶指南》“0x5B四边形不等式”指出：状态转移方程F[i]=min0≤j<i{F[j]+val(j,i)} ，若val满足四边形不等式，则F具有决策单调性，可以把DP计算F[i]的复杂度从O(N2)优化到O(NlogN) 。
08
例题
拿到题目后，先判断w是否单调、是否满足四边形不等式，再使用四边形不等式优化DP 。
1.石子合并
洛谷P1880
https://www.luogu.com.cn/problem/P1880
题目描述：
在一个圆形操场的四周摆放N堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法，计算出将N堆石子合并成1堆的最小得分和最大得分
输入：
数据的第1行是正整数N ，表示有N堆石子。
第2行有N个整数，第i个整数ai表示第i堆石子的个数。
输出：
输出共2行，第1行为最小得分，第2行为最大得分。
样例输入：
4
4594
样例输出：
43
54
题解：
（1）如果石子堆没有顺序，可以任意合并，用贪心法，每次选择最小的两堆合并。
（2）本题要求只能合并相邻的两堆，不能用贪心法。贪心操作是每次合并时找石子数相加最少的两堆相邻石子。例如环形石子堆开始是{2,4,7,5,4,3} ，下面用贪心得到最小值64 ，但是另一种方法得到63 。

文章图片
（3）用四边形优化DP求解石子合并的最小值，复杂度是O(n2) 。
状态转移矩阵dp[i][j]前文已有说明，这里不再赘述。
最小值用四边形不等式优化DP ， w在四边形不等式中取等号：w[i][j]+w[i′][j′]=w[i][j′]+w[i′][j] 。
本题的石子堆是环状的，转换为线形的更方便处理。复制和原来一样的数据，头尾接起来，使n的数列转化为2n的数列，变成线形的。
（4）这一题除了求最小值，还求最大值。虽然最大值也用DP求解，但是它不满足反四边形不等式的单调性要求，不能优化。而且也没有必要优化，可以用简单的推理得到：区间[i,j]的最大值，等于区间[i,j?1]和[i+1,j]中的最大值加上w(i,j) 。
（5）石子合并问题的最优解法是GarsiaWachs算法，复杂度O(nlogn) 。读者可以参考“洛谷P5569石子合并” ，这题N≤40000N≤40000N≤40000 ，用DP会超时。
1.最优二叉搜索树
最优二叉搜索树是Knuth（高纳德）解决的经典问题，是四边形不等式优化的起源。
OptimalBinarySearchTree
uva10304https://vjudge.net/problem/UVA-10304
题目描述：
给定n个不同元素的集合S=(e1,e2,...,en) ，有e1<e2<...<en ，把S的元素建一棵二叉搜索树，希望查询频率越高的元素离根越近。
访问树中元素ei的成本cost(ei)等于从根到该元素结点的路径边数。给定元素的查询频率f(e1) ， f(e2) ， ... ， f(en) ，定义一棵树的总成本是：
f(e1)?cost(e1)+f(e2)?cost(e2)+...+f(en)?cost(en)
总成本最低的树就是最优二叉搜索树。
输入：
输入包含多个实例，每行一个。每行以1≤n≤250开头，表示S的大小。在n之后，在同一行中，有n个非负整数，它们表示元素的查询频率， 0≤f(ei)≤100 。
输出：
对于输入的每个实例，输出一行，打印最优二叉搜索树的总成本。
样例输入：
15
3101010
351020
样例输出：
0
20
20
题解：
二叉搜索树（BST）的特点是每个结点的值，比它的左子树上所有结点的值大，比右子树上所有值小。二叉搜索树的中序遍历，是从小到大的排列。第3个样例的最优二叉搜索树的形状见下图，它的总成本是5?2+10?1=20 。

文章图片
▍图6二叉搜索树
题目给的元素已经按照从小到大排列，可以方便地组成一棵BST 。
设dp[i][j]是区间[i,j]的元素组成的BST的最小值。把区间[i,j]分成两部分[i,k?1]和[k+1,j] ， k在i和j之间滑动。用区间[i,j]建立的二叉树， k是根结点。这是典型的区间DP ，状态转移方程：