四边形不等式其实就是一个证明单调性的过程，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]满足四边形不等式。
