四边形不等式
设函数(w(x,y))是定义在(Z)上的函数，若对于任意(a,b,c,d in Z)，其中(aleq b leq c leq d)， 都有(w(a,d)+w(b,c)ge w(a,c)+w(b,d))，则称函数(w)满足四边形不等式
推论：
设函数(w(x,y))是定义在(Z)上的函数，若对于任意(a,b in Z)，其中(a<b)， 都有(w(a,b+1)+w(a+1,b) ge w(a,b)+w(a+1,b+1))，则函数(w)满足四边形不等式
证明：
对于(a<c)，有：
对于(a+1<c)，有：
两式相加，得：
整理得：
依此类推，对于任意(aleq b leq c)，有：
（此处即用(b)来代替(a+2)，因为(a+1 <c) ，所以(b leq c)）
同理，对于任意(aleq b leq c leq d)，有：
定理1
对于任意(a,b,c,d in Z)，如果函数(w)满足四边形不等式，且(w(a,d)ge w(b,c))，则函数(f)也满足四边形不等式，其中(f)满足：
（特别的，我们令(f(x,y)=w(x,y)=0)）
证明：
当(x+1=y)时，我们有：
若(f(x,x+2))的最优决策是(x+1)，则：
显然
若(f(x,x+2))的最优决策是(x)，则：
显然
而
所以当(x+1=y) 时，我们得到：
即此时四边形不等式成立。
接下来，我们运用数学归纳法
假设当(y-x<k)时，四边形不等式成立。
我们现在考虑(y-x=k)的情况
令(f(x,y+1))以(a)为最优决策，(f(x+1,y))以(b)为最优决策。
不妨设(x+1leq a leq b)
易得：
对于(f(x,y))和(f(x+1,y+1))，由于(a)，(b)不一定是最优决策，所以我们有：
因为(w)满足四边形不等式，所以：
根据归纳假设，我们有：
于是我们有：
定理2:
对于任意(a,b,c,d in Z)，如果函数(w)满足四边形不等式，且函数(f)满足：
（特别的，我们令(f(x,y)=w(x,y)=0)）
记(P(x,y))为令(f(x,y))取到最小值的(k)值。如果函数(f)满足四边形不等式，那么对于任意(x)，(y)，我们有：
证明：
记(p=P(i,j))。
对于任意的(x< k leq p)，由四边形不等式得：
移项得：
由于(p)为最优决策，所以我们有：
所以：
这意味着，对于(f(x+1,y)) 的任意决策(kleq p)，(p)都要比(k)更优（包括相等）
所以
同理可证
所以
例题
1.[NOI1995]石子合并
现在有(n)堆石子(环状)， 每次只能将相邻的两堆合并成一堆，每次的得分是两队石子之和，求最大得分和最小得分
显然，本题是区间dp。
令(dp[i][j])表示(i)到(j)之间合并石子的最小值（最大值同理），则我们可以很轻松地列出状态转移方程为：
其中(d(i,j))表示(i)到(j)之间石子的个数
当问题是最小值时，我们就可以用四边形不等式优化了。此时，对于(dp[i][j])，我们只需要在区间([P[i][j-1],P[i+1][j]])枚举(k)即可，时间复杂度为(O(n^2))
注意：最大值并不满足单调性，不能用四边形不等式优化，但此时最大值有一个性质：
使最大值最优的决策(P[i][j])要么是(i)，要么是(j-1)
证明：
反证法。
假设最优决策(P[i][j]=p)，且(i<p<j-1)
我们有两种情况：
情况一：(d(i,p)leq d(p+1,j))
我们可以令(t=P[i][p])，于是此时我们的方案便是：
({[i,i+1,i+2,...,t|t+1,t+2,...,p]p+1,p+2,...j})
得分(F_1=(dp[i][t]+dp[t+1][p]+d(i,p))+dp[p+1][j]+d(i,j))
此时我们可以构造一种方案：
({i+1,i+2,...,t[t+1,t+2,...,p|p+1,p+2,...j]})
得分(F_2=dp[i][t]+(dp[t+1][p]+dp[p+1][j]+d(t+1,j))+d(i,j))
因为(t<p)，所以(d(i,p)leq d(p+1,j< d(t+1,j))
所以(F_1< F_2)，即此时决策(p)并不是最优
情况二：(d(i,p)>d(p+1,j))
同样的，我们令(t=P[p+1][j])，此时我们的方案：
({i,i+1,i+2,...,p[p+1,p+2,...,t|t+1,t+2,...j]})
得分(F_1=dp[i][p]+(dp[p+1][t]+dp[t+1][j]+d(p+1,j))+d(i,j))
我们仍然可以构造一种方案：
({[i,i+1,i+2,...,p|p+1,p+2,...,t]t+1,t+2,...j})
得分(F_2=(dp[i][p]+dp[p+1][t]+d(i,t+1))+dp[t+1][j]+d(i,j))
因为(t+1>p)，所以(d(i,t+1)>d(i,p)>d(p+1,j))
所以(F_1<F_2)，即此时决策(p)仍然不是最优
这与假设矛盾，所以最优决策只可能是(i)或者$j-1 $
Code：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int dp[maxn][maxn];
int dp2[maxn][maxn];
int n;
int a[maxn];
int sum[maxn];
int p[maxn][maxn];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i+n]=a[i];
for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i],p[i][i]=i;
for(int i=n<<1;i>=1;i--)
for(int j=i+1;j<=n<<1;j++){
dp[i][j]=0x3f3f3f3f;
dp2[i][j]=max(dp2[i][i]+dp2[i+1][j],dp2[i][j-1]+dp2[j][j])+sum[j]-sum[i-1];
for(int k=p[i][j-1];k<=p[i+1][j];k++)
if(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]<dp[i][j]){
dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
p[i][j]=k;
}else if(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]==dp[i][j])
p[i][j]=max(p[i][j],k);
}
int ans=0x3f3f3f3f;
int ans2=0;
for(int i=1;i<=n;i++) ans=min(ans,dp[i][i+n-1]);
for(int i=1;i<=n;i++) ans2=max(ans2,dp2[i][i+n-1]);
printf("%d
%d
",ans,ans2);
return 0;
}
参考文献：
1.李煜东《算法竞赛进阶指南》
2.2001年国家集训队论文 毛子青《动态规划算法的优化技巧》