在DP优化中，怎么证明四边形不等式

四边形不等式其实就是一个证明单调性的过程，noip是铁定用不着的，noi理论上讲应该会考，但也很少见过这方面的题目，学会石子合并的四边形不等式优化就差不多了，网上的东西都不大好，我给你讲解一下：题目描述：有n堆石子排成一条直线，每堆石子有一定的重量。现在要合并这些石子成为一堆石子，但是每次只能合并相邻的两堆。每次合并需要消耗一定的体力，该体力为所合并的两堆石子的重量之和。问最少需要多少体力才能将n堆石子合并成一堆石子？ 数据规模:nlt=3000 样例输入: 8 5 2 4 7 6 1 3 9 样例输出: 105 分析：令m[i,j]表示归并第i个数到第j数的最小代价,w[i,j]表示第i个数到第j个数的和，这个可以事先计算出来。w可以在O(n^2)的时间内算出.关于w[i,j]的优化方法:令t[i]表示 a[1]到a[i]的和, t[i]可以在输入数据时用O(n)的时间算出然后w[i,j] = t[j]-t[i-1]有如下的状态转移方程: m[I,j]=0(i=j的时候)，min{m[I,k]+m[k+1,j]}+w[I,j]} 阶段：以归并石子的长度为阶段，一共有n-1个阶段。状态：每个阶段有多少堆石子要归并，当归并长度为2时，有n-1个状态；当归并长度为3时，有n-2个状态；当归并长度为n时，有1个状态。决策：当归并长度为2时，有1个决策；当归并长度为3时，有2个决策；当归并长度为n时，有n-1个决策。for len := 2 to n dofor i := 1 to n - len + 1 do begin j := i + len - 1 f[i,j] := MAXINT for k:= i+1 to j do begin 参考上面状态转移方程求解 end不难发现这个算法的复杂度是n^3。n的范围是3000，需要优化算法。对于动态规划的优化和搜索的优化是一样的道理。搜索中，如果某状态下不会有最优解，那么就不用继续搜索下去了。动态规划也可以这样来优化。具体方法是：在计算每个状态的值的时候，记录下它所选取的分界点k，用s[i,j]表示当m[i,j]取最优值的时候，选取的k值。那么原状态转移方程中的k的枚举范围便可以从原来的(i+1~j)变为(s[i,j-1]~s[i+1,j]) 当函数w[i,j]满足： w[i,j] + w[i‘，j’] lt= w[i‘,j] + w[i,j’] (ilt=i‘ltjlt=j’) 时， 称w满足四边形不等式。 单调性：当函数w[i,j]满足： w[i’,j] lt= w[i,j’] (ilt=i‘ltjlt=j’) 时, 称w满足关于区间包含的单调性。 （至于为什么，我也不大会证，把结论记住就好，这个上了大学再研究）这样，对于状态转移方程式：m[i,j]=min{m[i,k-1]+m[k,j]+w[i,j]} (iltklt=j)

如果w[i,j]满足四边形不等式和区间包含单调性，那么m[i,j]也满足四边形不等式。 用s[i,j]表示m[i,j]的决策，如果函数m[i,j]满足四边形不等式，则函数s[i,j]满足单调性，即决策单调性： s[i,j]lt=s[i,j+]lt=s[i+1,j+1]。

则函数s[i,j]的值应该在一个区间内，即： s[i,j-1] lt= s[i,j] lt= s[i+1,j] 由于s[i,j-1]和s[i+1,j]已经在阶段j-i求出，所以在枚举决策变量k时，就可以从s[i,j-1]到s[i+1,j]。于是，我们利用s[i,j]的单调性，得到优化的状态转移方程为：m[I,j]=min{m[I,k]+m[k+1,j]}+w[I,j] 利用这样的决策单调性，就可以把时间复杂性优化到O(n^2)。边界：s[i,i] = i s[i,j]的值在m[i,j]取得最优值时，保存、更新。 上述方法是具有普遍性的。对于状态转移方程与上述类似，且w[i,j]满足四边形不等式的动态规划问题，都可以采用相同的优化方法，如最优二叉排序树（NOI`96）等。费了不少功夫，给个满意答案吧。

考研七个基本不等式是如下：

一、基本不等式

√(ab)≤(a+b)/2，那么可以变为 a^2-2ab+b^2 ≥ 0，a^2+b^2 ≥ 2ab，ab≤a与b的平均数的平方。

二、绝对值不等式公式

| |a|-|b| |≤|a-b|≤|a|+|b|。

| |a|-|b| |≤|a+b|≤|a|+|b|。

三、柯西不等式

设a1,a2,an,b1,b2，bn均是实数，则有(a1b1+a2b2++anbn)^2≤(a1^2+a2^2+an^2)*(b1^2+b2^2+bn^2) 当且仅当ai=λbi(λ为常数，i=1,2.3,n)时取等号。

四、三角不等式

对于任意两个向量b其加强的不等式，这个不等式也可称为向量的三角不等式。

五、四边形不等式

如果对于任意的a1≤a2<b1≤b2，有m[a1,b1]+m[a2,b2]≤m[a1,b2]+m[a2,b1]，那么m[i,j]满足四边形不等式。

课程：

（1）基本算法: 二分,分治，贪心

（2） 离散数学离散数学动态规划

（3） 搜索算法：深度优先 搜索，广度优先搜 A*算法 ，阿尔法贝塔剪枝

（4）数据结构:  线段树, 树状数组，并查集,Trie图

（5）图论问题：最小生成树 最短路 强连通分量、桥和割点

（6）网络流算法：基本的网络流算法，Dinic算法，带上下界的网络流，最小费用流

（7）计算几何：线与线求交，线与面求交，求凸包，半平面求交等

（8） 离散数学，高等数学，线性代数，初等数论，计算几何

（9）计算机专业英语

（10）C++；基础的递归、枚举算法

扩展资料：

1.参赛队伍最多由三名参赛队员组成。

2.竞赛中命题10题左右，试题描述为英文，比赛时间为5个小时，前四个小时可以实时看到排名，最后一小时封榜，无法看到排名。

3.竞赛可以使用的语言：Java, C, C++, Kotlin 和 Python。

4.重点考察选手的算法和程序设计能力，不考察实际工程中常用的系统编程，多线程编程等等；

5.选手可携带任何非电子类资料，包括书籍和打印出来的程序等，部分赛区会对选手携带的纸质资料做限制。

6.评委负责将结果（正确或出错的类型）通过网络尽快返回给选手，除此之外不提供任何额外帮助；

7.每个题目对应一种颜色的气球，通过该题目的队伍会得到对应颜色气球。每道题目第一支解决掉它的队还会额外获得一个“FIRST PROBLEM SOLVED”的气球。

参考资料：北京大学暑期课：ACM/ICPC竞赛训练

百度百科-ACM国际大学生程序设计竞赛

---