四边形不等式&决策单调性优化dp

## 四边形不等式
### 1.四边形不等式

对于 $a\le b\le c\le d$ 和定义域为整数域的二元函数 $w$，若有
$$w(a,d)+w(b,c)\ge w(a,c)+w(b,d)$$
则称 $w$ 满足四边形不等式

### 2.拓展形式
对于 $a\le b$ 和定义域为整数域的二元函数 $w$，若有
$$w(a,b+1)+w(a+1,b)\ge w(a,b)+w(a+1,b+1)$$
则称 $w$ 满足四边形不等式

### 3.区间包含单调性

对于 $a\le b\le c\le d$ 和定义域为整数域的二元函数 $w$，若有
$$w(a,d)\ge w(b,c)$$
则称 $w$ 满足区间包含单调性

### 4.性质
* 性质1：若函数 $w_1(l,r),w_2(l,r)$ 均满足四边形不等式（或区间包含单调性），则对于任意 $c_1,c_2\ge0$，函数 $c_1w_1+c_2w_2$ 也满足四边形不等式（或区间包含单调性）。

* 性质2：若存在函数 $f(x),g(x)$ 使得 $w(l,r)=f(r)-g(l)$，则函数 $w$ 满足四边形不等式。当 $f,g$ 单调增加时，函数 $w$ 还满足区间包含单调性。

* 性质3：设 $h(x)$ 为一单调增加的下凸函数，若函数 $w(l,r)$ 满足四边形不等式且满足区间包含单调性，则复合函数 $h(w(l,r))$ 也满足四边形不等式和区间包含单调性。

* 性质4：设 $h(x)$ 为一下凸函数，若函数 $w(l,r)$ 满足四边形不等式且满足区间包含单调性，则复合函数 $h(w(l,r))$ 也满足四边形不等式。

这里不给出证明。

## 模板
### 形式1
求 $f_i=\min\ w(j,i)\ \ \ (1\le j\le i\le n)$

这里以及下文都假定成本 $w(j,i)$ 可以在 $O(1)$ 时间内计算

默认从1开始编号

### code1
```cpp
typedef long long LL;
LL n,f[N];
LL w(LL j,LL i) { return ...; }//区间j->i的成本
void DP(LL l,LL r,LL k_l,LL k_r)
{
	if(l>r) return;
	LL mid=l+r>>1,k=k_l;
	for(int i=k_l;i<=min(k_r,mid);i++)
		if(w(i,mid)<w(k,mid)) k=i;
	f[mid]=w(k,mid);
	DP(l,mid-1,k_l,k);
	DP(mid+1,r,k,k_r);
}
```

### 形式2
求 $f_i=\min\ f_j+w(j+1,i)\ \ \ (0\le j<i\le n)$

### code2
```cpp
typedef long long LL;
LL n,L,c[N],f[N],q[N],hh,tt,rt[N],lt[N];
LL w(LL i,LL j) { return .../*区间j+1->i的成本*/+f[j]; }
void solve()
{
	q[0]=0;
	lt[0]=1;
	rt[0]=n;
	for(int i=1;i<=n;i++)
	{
		while(hh<=tt&&rt[q[hh]]<i) hh++;
		lt[q[hh]]=i;
		f[i]=w(i,q[hh]);
		while(hh<=tt&&w(lt[q[tt]],i)<w(lt[q[tt]],q[tt])) tt--;
		if(hh>tt)
		{
			q[++tt]=i;
			lt[i]=i+1;
			rt[i]=n;
		}
		else if(w(rt[q[tt]],q[tt])<w(rt[q[tt]],i))
		{
			if(rt[q[tt]]<n)
			{
				q[++tt]=i;
				lt[i]=rt[q[tt-1]]+1;
				rt[i]=n;
			}
		}
		else
		{
			LL l=lt[q[tt]],r=rt[q[tt]],mid;
			while(l+1<r)
			{
				mid=l+r>>1;
				if(w(mid,i)<w(mid,q[tt])) r=mid;
				else l=mid;
			}
			rt[q[tt]]=l;
			q[++tt]=i;
			lt[i]=r;
			rt[i]=n;
		}
	}
}
```

### 形式3
求 $f(k,i)=\min\ f(k-1,j-1)+w(j,i)\ \ \ (1\le k \le m,1\le i \le n)$

### code3
```cpp
typedef long long LL;
LL w(LL i,LL j) { return .../*区间i->j的成本*/; }
void solve()
{
	for(int i=1;i<=n;i++)
	{
		f[1][i]=w(1,i);
		opt[1][i]=1;
	}
	for(int i=2;i<=k;i++)
	{
		for(int j=n;j>=i;j--)
		{
			LL s=opt[i-1][j],t=opt[i][j+1],res=s;
			if(j==n) t=n;
			for(int o=s+1;o<=t;o++)
				if(f[i-1][o-1]+w(o,j)<f[i-1][res-1]+w(res,j))
					res=o;
			f[i][j]=f[i-1][res-1]+w(res,j);
			opt[i][j]=res;
		}
	}
	printf("%lld",f[k][n]);
}
```

### 形式4
求 $f(i,j)=\min f(i,k)+f(k+1,j)+w(i,j)\ \ \ (1\le i \le j \le n,i\le k<j)$
### code4
```cpp
typedef long long LL;
LL n,f[N][N],opt[N][N];
LL w(LL i,LL j) { return ...; }//区间i->j的成本
void solve()
{
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			f[i][j]=1e18;
	for(int i=1;i<=n;i++)
	{
		f[i][i]=0;
		opt[i][i]=i;
	}
	for(int len=2;len<=n;len++)
		for(int i=1;i<=n-len+1;i++)
		{
			int j=i+len-1;
			for(int o=opt[i][j-1];o<=opt[i+1][j];o++)
				if(f[i][j]>f[i][o]+f[o+1][j]+w(i,j))
				{
					f[i][j]=f[i][o]+f[o+1][j]+w(i,j);
					opt[i][j]=o;
				}
		}
}
```

正在渲染内容...