前言

之前写过一篇关于斜率优化的文章：Link

下面介绍另一种利用决策单调性来转移优化的方法。

算法简介

如果子问题的数目为 (Theta(n^2))，每个子问题需要用到 (Theta(n)) 个子问题的结果来转移，那么我们称它为 2D/1D 的问题。

一般来说，它的状态转移方程是这样子的：

[dp[i][j]=min_{ileq k<j}{dp[i][k]+dp[k+1][j]}+val(i,j)
]

不难发现，这是区间 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]) 得到：

[egin{align*}& dp[i][j]+dp[i+1][j+1]\&leq dp[i][x]+dp[x+1][j]+val(i,j)+dp[i+1][y]+dp[y+1][j+1]+val(i+1,j+1)\&leq dp[i][x]+dp[x+1][j+1]+val(i,j+1)+dp[i+1][y]+dp[y+1][j]+val(i+1,j)\&leq dp[i][j+1]+dp[i+1][j]end{align*}
]

得证！

性质 (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]) 即可。

[egin{align*}& (dp[i+1][j]-h[k][i+1][j])-(dp[i][j]-h[k][i][j])\&=(dp[i+1][j]+h[k][i][j])-(h[k][i+1][j]+dp[i][j])\&leq (dp[i+1][d]+dp[d+1][j]+dp[i][k]+dp[k+1][j])-(dp[i+1][k]+dp[k+1][j]+dp[i][d]+dp[d+1][j])\&=(dp[i+1][d]+dp[i][k])-(dp[i+1][k]+dp[i][d])end{align*}
]

由于 (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[i][j]=min_{ileq k<j}{dp[i][k]+dp[k+1][j]}+sum[j]-sum[i-1]
]

这里按照上面的证明过程，不难得到 (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;
}

练习题

山区建小学

[IOI2000]邮局