区间包含单调性：$\forall l_1\le l_2\le r_1\le r_2\to f(l_2,r_1)\le f(l_1,r_2)$。

四边形不等式：$\forall l_1\le l_2\le r_1\le r_2\to f(l_1,r_1)+f(l_2,r_2) \le f(l_2,r_1)+f(l_1,r_2)$。

$$ f_{l,r}=\min_{k=l}^{r-1}(f_{l,k}+f_{k+1,r})+w(l,r) $$

若 $w(l,r)$ 满足区间包含单调性和四边形不等式，则 $f(l,r)$ 满足四边形不等式。

记 $g(l,r)$ 为最小最优决策点，即 $f_{l,g(l,r)}+f_{g(l,r)+1,r}=\min_{k=l}^{r-1}(f_{l,k}+f_{k+1,r})$

若 $f(l,r)$ 满足四边形不等式，则 $g(l,r-1)\le g(l,r)\le g(l+1,r)$。

于是状态转移时顺便维护 $g(l,r)$，总时间复杂度 $\sum_{l=1}^n\sum_{r=l+1}^n g(l+1,r)-g(l,r-1)=\sum_{i=1}^n g(i,n)-g(1,i)\le n^2$。

洛谷p1880

题意

给定一个环，环上有 $n$ 堆石头，每次可以合并两堆相邻的石头，费用为两堆石头的数量和，求将所有石头合并到一堆的最小和最大费用。

题解

首先把环倍增成两倍长的链。最小费用状态转移同类型一，易知 $w$ 满足区间包含单调性和四边形不等式。

最大费用考虑贪心，每次都是操作上一次合并的石头堆和与其相邻的石头堆，有 $f_{l,r}=\max(f_{l,r-1}+f_{l+1,r})+w(l,r)$。

const int MAXN=205,Inf=1e8;
int dp1[MAXN][MAXN],dp2[MAXN][MAXN],g[MAXN][MAXN],s[MAXN],a[MAXN];
int main()
{
	int n=read_int();
	_rep(i,1,n)a[i]=a[i+n]=read_int();
	_rep(i,1,n*2){
		s[i]=s[i-1]+a[i];
		g[i][i]=i;
	}
	_rep(i,1,2*n)_rep(j,i+1,2*n)dp1[i][j]=Inf;
	for(int i=n*2-1;i;i--)_rep(j,i+1,n*2){
		_rep(k,g[i][j-1],g[i+1][j]){
			if(dp1[i][k]+dp1[k+1][j]+s[j]-s[i-1]<dp1[i][j]){
				dp1[i][j]=dp1[i][k]+dp1[k+1][j]+s[j]-s[i-1];
				g[i][j]=k;
			}
		}
		dp2[i][j]=max(dp2[i+1][j],dp2[i][j-1])+s[j]-s[i-1];
	}
	int ans1=Inf,ans2=0;
	_rep(i,1,n){
		ans1=min(ans1,dp1[i][i+n-1]);
		ans2=max(ans2,dp2[i][i+n-1]);
	}
	enter(ans1);
	enter(ans2);
	return 0;
}

$$ f_r=\min_{l=l}^{r-1}(f_{l}+w(l,r)) $$

若 $w(l,r)$ 满足四边形不等式，则 $f$ 具有决策单调性。记 $g(i)$ 为最小最优决策点，则 $g(i)\le g(i+1)$。

考虑单调队列二分，维护每个元素的原始位置 $p$ 和负责的优决策区间 $[l,r]$。

每次新加入一个点 $i$，如果该点对序列末尾 $n$ 的决策不如队列末尾的点，则无视该点。

否则和队列末尾的点比较在 $l_\text{tail}$ 位置的决策，如果 $i$ 更优则删去末尾的点，不断操作直到 $i$ 不再更优。

最后 $i$ 和队列末尾点的最优决策分界点一定位于区间 $[l_\text{tail},r_\text{tail}]$，二分查找即可。时间复杂度 $O(n\log n)$。

洛谷p3195

题意

题解