前言
之前写过一篇关于斜率优化的文章：Link
下面介绍另一种利用决策单调性来转移优化的方法。
算法简介
如果子问题的数目为 (Theta(n^2))，每个子问题需要用到 (Theta(n)) 个子问题的结果来转移，那么我们称它为 2D/1D 的问题。
一般来说，它的状态转移方程是这样子的：
不难发现，这是区间 DP 的常用方程。
如果直接进行状态转移，那么时间复杂度为 (Theta(n^3))。
但是，如果 (val(i,j)) 存在某些特殊的性质，我们就可以用四边形不等式对其进行优化。
这里先介绍一下四边形不等式：
-
定义 (1)：如果 (forall lleq l'leq r'leq r,f(l,r')+f(l',r)leq f(l',r')+f(l,r))，则称函数 (f) 满足四边形不等式。
-
定义 (2)：如果 (forall lleq l'leq r'leq r,f(l',r')leq f(l,r))，则称函数 (f) 满足区间包含单调性。
下面详细介绍一下关于它的一些小性质：
-
性质 (1)：函数 (f) 满足四边形不等式，当且仅当 (forall i<j,f(i+1,j)+f(i,j+1)leq f(i,j)+f(i+1,j+1))。
-
性质 (2)：在上面的状态转移方程中，若 (val) 满足区间包含单调性和四边形不等式，则 (dp) 也满足四边形不等式。
-
性质 (3)：在上面的状态转移方程中，设 (dp) 的决策为 (s)，且 (dp) 满足四边形不等式，则 (s[i][j-1]leq s[i][j]leq s[i+1][j])。
关于上面性质的证明如下：
- 性质 (1) 的证明：
用数学归纳法解释，比较简单。
- 性质 (2) 的证明：
考虑对区间长度归纳。
当区间长度为 (1,2) 时，不难证明四边形不等式成立。
假设当区间长度 (<j-i+1) 时，四边形不等式成立，下面证明当区间长度 (=j-i+1) 时成立。
相当于去证明这个式子：(dp[i][j]+dp[i+1][j+1]leq dp[i][j+1]+dp[i+1][j])
设 (dp[i+1][j]) 是由 (k=x) 转移得到，(dp[i][j+1]) 是由 (k=y) 转移得到，不妨设 (xleq y)。
这里先证明一下：(dp[x+1][j]+dp[y+1][j+1]leq dp[x+1][j+1]+dp[y+1][j])。
事实上，由归纳假设我们知道：(dp[x+1][j]-dp[x+1][j+1]leq dp[x+2][j]-dp[x+2][j+1])。
以此类推即可得到上面我们想证的式子是成立的。
此时将 (k=x) 代入 (dp[i][j])，将 (k=y) 代入 (dp[i+1][j+1]) 得到：
得证！
- 性质 (3) 的证明：
先证明：(s[i][j]leq s[i+1][j])。
我们设 (dp[i][j]) 是由 (s[i][j]=d) 转移得到的。
设 (h[k][i][j]=dp[i][k]+dp[k+1][j],forall k<d)。
那么有 (dp[i][j]leq h[k][i][j])，接下来只需证明：(dp[i+1][j]leq h[k][i+1][j]) 即可。
由于 (dp) 满足四边形不等式，故我们有：(forall i+1leq k<d,dp[i+1][d]+dp[i][k]leq dp[i+1][k]+dp[i][d])。
因此，(dp[i+1][j]-h[k][i+1][j]leq dp[i][j]-h[k][i][j]leq 0)。
于是，(s[i][j]leq s[i+1][j])。
同理可得：(s[i][j-1]leq s[i][j])。
得证！
例题讲解
下面提供一道较为基础的题目：
例题1：[NOI1995]石子合并
(Large{ ext{Description:}})
在一个圆形操场的四周摆放 (n) 堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记为该次合并的得分。
需要计算出将 (n) 堆石子合并成一堆的最小得分和最大得分。
数据范围：(nleq 100)。
(Large{ ext{Solution:}})
首先，这题可以想到用区间 DP 求解，再加上断环成链的思想，我们可以考虑到上面说的 2D/1D 的常规状态转移方程：
最大值比较简单，直接取两个端点的最大值即可；
最小值需要用下面的状态转移方程来实现：
这里按照上面的证明过程，不难得到 (dp) 是满足四边形不等式的。
那么利用性质 (2,3) 就可以写出下面的代码……（四边形不等式的优化大致上就是一个模板，会灵活应用即可）
时间复杂度：(Theta(n^2))。
(Large{ ext{Code:}})
#include<bits/stdc++.h>
#define Re register
using namespace std;
const int N=205;
int n,a[N],sum[N];
int DP[N][N];
int s[N][N],dp[N][N];
inline int rd()
{
char ch=getchar();
int x=0,f=1;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
scanf("%d",&n);
for(Re int i=1;i<=n;i++)
{
a[i]=rd();
a[n+i]=a[i];
}
for(Re int i=1;i<=n+n;i++)
{
sum[i]=sum[i-1]+a[i];
s[i][i]=i;
}
for(Re int i=n+n;i>0;i--)
{
for(Re int j=i+1;j<=n+n;j++)
{
DP[i][j]=max(DP[i+1][j],DP[i][j-1])+sum[j]-sum[i-1];
int Mindp=0x3f3f3f3f,Mins;
for(Re int k=s[i][j-1];k<=s[i+1][j];k++)
{
if(Mindp>dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])
{
Mindp=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
Mins=k;
}
}
dp[i][j]=Mindp;
s[i][j]=Mins;
}
}
int ans1=0x3f3f3f3f,ans2=0;
for(Re int i=1;i<=n+1;i++)
{
ans1=min(ans1,dp[i][i+n-1]);
ans2=max(ans2,DP[i][i+n-1]);
}
printf("%d
%d",ans1,ans2);
return 0;
}