简单四边形不等式优化dp（下）

广义决策单调性

强烈推荐题解视频

设$f_{k,i}$表示前$i$个村庄放了$k$个邮局的最小代价。

则 f k , i = min ⁡ j = 0 i { f k − 1 , j + w j + 1 , i } f_{k,i}=\overset{i}{\underset{j=0}\min}\{f_{k-1,j}+w_{j+1,i}\} fk,i​=j=0min​i​{fk−1,j​+wj+1,i​}
表示分配给村庄$[j+1,i]$一个邮局。

设$f_{0,0}=0$，其他状态为正无穷。就是$O(n^3)$

贡献函数$w_{i,j}$表示给村庄$[i,j]$分配一个邮局的最小贡献。
显然邮局放在区间下标中位数对应的村庄最优。如果有偶数个村庄放在两个中位数处都可以。
因为如果向着远离中位数的地方移动，那么减少的贡献少，而增加的贡献多。

则$w_{i,j}=w_{i,j-1}+a_j-a_{\lfloor \frac{i+j}{2}\rfloor }$
因为当区间长度由奇数向偶数转移时中位数不变，式子肯定成立。
而区间长度为偶数时可以认为邮局位于右边那个中位数处，中位数也可以认为不变。

打表打出决策单调性，于是可以$O(n^2)$：
f k , i = min ⁡ j = p k − 1 , i p k , i + 1 { f k − 1 , j + w j + 1 , i } f_{k,i}=\overset{p_{k,i+1}}{\underset{j=p_{k-1,i}}\min}\{f_{k-1,j}+w_{j+1,i}\} fk,i​=j=pk−1,i​min​pk,i+1​​{fk−1,j​+wj+1,i​}

#include
#include
#include
using namespace std;
const int N=3e3;
int a[N+5];
int w[N+5][N+5];
int f[305][N+5],p[305][N+5];
int main() {
	int n,K;
	cin>>n>>K;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<=n; i++)
		for(int j=i; j<=n; j++)
			w[i][j]=w[i][j-1]+a[j]-a[i+j>>1];
	for(auto&i:f) for(auto&j:i) j=1e9;
	f[0][0]=0;
	for(int i=1;i<=K;i++) p[i][n+1]=n;注意最优决策点要有初值
	for(int k=1; k<=K; k++)
		for(int i=n; i; i--)因为在枚举i时用到的i+1的最优决策点，因此要倒序枚举
			for(int j=p[k-1][i]; j<=p[k][i+1]; j++)
//			for(int j=0; j<=i-1; j++)
				if(f[k][i]>f[k-1][j]+w[j+1][i])
					f[k][i]=f[k-1][j]+w[j+1][i],p[k][i]=j;
//				f[k][i]=min(f[k][i],f[k-1][j]+w[j+1][i]);
	cout<<f[K][n]<<endl;
//	for(int k=1;k<=K;k++,cout<
//		for(int i=1;i<=n;i++,cout<<' ')
//			cout<
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

证明决策单调性还是老三样：

1. 证明贡献函数满足四边形不等式：
   带入递推式$w_{i,j}=w_{i,j-1}+a_j-a_{\lfloor \frac{i+j}{2}\rfloor }$就会发现贡献函数显然满足四边形不等式：
   $w_{i,j}+w_{i+1,j+1}\le w_{i,j+1}+w_{i+1,j}$
   $w_{i,j}+w_{i+1,j}+w_{i+1,j}+a_{j+1}-a_{\lfloor \frac{i+j-2}{2}\rfloor }\le w_{i,j}+a_{j+1}-a_{\lfloor \frac{i+j-1}{2}\rfloor }+w_{i+1,j}$
2. 证明状态函数满足四边形不等式：
   不需要归纳，直接设$p_{i,j+1}=x,p_{i+1,j}=y$，我们讨论$x<y$的情况：
   两个含有$f_{i,j},f_{i+1,j+1}$的不等式：
   { f i , j ≤ f i − 1 , x + w x + 1 , j              f i + 1 , j + 1 ≤ f i , y + w y + 1 , j + 1 \left\{
   fi,j≤fi−1,x+wx+1,j\textcolorbluefi+1,j+1≤fi,y+wy+1,j+1" role="presentation" style="position: relative;">fi,j≤fi−1,x+wx+1,j\textcolorbluefi+1,j+1≤fi,y+wy+1,j+1$$\begin{array}{c}{f}_{i,j}\le f_{i-1,x}+w_{x+1,j}\\ \text{textcolor}blue{f}_{i+1,j+1}\le f_{i,y}+w_{y+1,j+1}\end{array}$$
   \right. {fi,j​≤fi−1,x​+wx+1,j​fi+1,j+1​≤fi,y​+wy+1,j+1​​
   加起来：$f_{i,j}+f_{i+1,j+1}\le f_{i-1,x}+w_{x+1,j}+f_{i,y}+w_{y+1,j+1}$
   再加上两个含有$f_{i,j+1},f_{i+1,j}$的等式
   { f i , j + 1 = f i − 1 , x + w x + 1 , j + 1 f i + 1 , j = f i , y + w y + 1 , j                \left\{
   fi,j+1=fi−1,x+wx+1,j+1fi+1,j=fi,y+wy+1,j" role="presentation" style="position: relative;">fi,j+1=fi−1,x+wx+1,j+1fi+1,j=fi,y+wy+1,j$$\begin{array}{c}{f}_{i,j+1}=f_{i-1,x}+w_{x+1,j+1}\\ f_{i+1,j}=f_{i,y}+w_{y+1,j}\end{array}$$
   \right. {fi,j+1​=fi−1,x​+wx+1,j+1​fi+1,j​=fi,y​+wy+1,j​​
   加到不等式的右边去：
   $f_{i,j}+f_{i+1,j+1}+f_{i-1,x}+w_{x+1,j+1}+f_{i,y}+w_{y+1,j}\le f_{i,j+1}+f_{i+1,j}+f_{i-1,x}+w_{x+1,j}+f_{i,y}+w_{y+1,j+1}$
   $f_{i,j}+f_{i+1,j+1}+w_{x+1,j+1}+w_{y+1,j}\le f_{i,j+1}+f_{i+1,j}+w_{x+1,j}+w_{y+1,j+1}$
   对不等式左边用贡献函数的四边形不等式：
   $f_{i,j}+f_{i+1,j+1}+w_{x+1,j}+w_{y+1,j+1}\le f_{i,j+1}+f_{i+1,j}+w_{x+1,j}+w_{y+1,j+1}$
   约掉了：
   $f_{i,j}+f_{i+1,j+1}\le f_{i,j+1}+f_{i+1,j}$
   证毕。（另一种情况同理）
3. 证明决策单调性：
   打出表来会知道决策单调性是$p_{i-1,j}\le p_{i,j}\le p_{i,j+1}$。
   接下来证明左边，假设不成立，设$p_{i,j}=p,p_{i-1,j}=k$，则：$p<k$
   先写出两个决策点在$f_{i-1,j}$意义下的最优性：
   $A:f_{i-1,k}\le f_{i-1,p}$
   再写出我们期望它们在$f_{i,j}$意义下的最优性：
   $B:f_{i,k}\le f_{i,p}$
   设$A+T=B$，用还原不等式的方法会发现，$T$恰为四边形不等式，则$B$得证。
   因此$f_{i,k}\le f_{i,p},f_{i,k}\ge f_{i,p}$，则$f_{i,k}=f_{i,p}$，说明$k$与$p$在$f_{i,j}$意义上一样优。因此决策单调性得证。

二维四边形不等式优化dp

题解视频

首先考虑考虑设状态：
二叉搜索树的一个子树对应有序序列上一个连续的区间，因为中序遍历要递增。所以一眼区间dp。考虑到贡献与层数有关，我们需要把状态写进层数：
设$f_{k,i,j}$表示目前区域根节点深度为$k$，区间为$[i,j]$的最小贡献。
这个dp很明显是$O(n^4)$的，但是十秒钟…也可以过。

但是今天说的是四边形不等式优化dp。
我们首先考虑一下如何把状态优化为$O(n^2)$，一般来说牵扯到因为贡献计算而需要增加状态维数的问题，主要有三种计算费用的方法：

1. 费用提前计算，例如任务安排
2. 费用即时计算，也就是我们现在这种写法
3. 费用推迟计算，主要的想法是从$i,j$转移的贡献只与$i,j$有关，与$k$无关，那我们可以等到转移的时候从后继计算贡献。
   （不过好像这么简单的技巧应该不需要总结）

因此设$f_{i,j}$表示区间$[i,j]$构成了一颗子树，且假设根深度为$0$时的贡献，则可以写出转移，转移就是枚举选择$k$为根：
f i , j = min ⁡ k = i j { f i , k − 1 + f k + 1 , j + w k ( i , j ) } f_{i,j}=\overset{j}{\underset{k=i}\min}\{f_{i,k-1}+f_{k+1,j}+w_k(i,j)\} fi,j​=k=imin​j​{fi,k−1​+fk+1,j​+wk​(i,j)}

设数字用$a$表示，$s$表示$a$的前缀和，则其中贡献函数$w_k(i,j)=s_j-s_{i-1}+a_k$

时间复杂度$O(n^3)$，足够通过本题了，但是还可以做到更优。

打表打出决策单调性，$p_{i,j-1}\le p_{i,j}\le p_{i+1,j}$，可以优化为$O(n^2)$

#include
#include
#include
using namespace std;
const int N=250;
int f[N+5][N+5],p[N+5][N+5];
int a[N+5],s[N+5];
int main() {
	int n;
	for(int i=1;i<=N;i++) p[i][i]=i;
	while(cin>>n) {
		for(int i=1;i<=n;i++) (cin>>a[i]),s[i]=s[i-1]+a[i];
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++) f[i][j]=1e9;
		for(int len=2;len<=n;len++)
			for(int i=1,j;(j=i+len-1)<=n;i++) 
//				for(int k=i;k<=j;k++)
				for(int k=p[i][j-1];k<=p[i+1][j];k++)
					if(f[i][j]>f[i][k-1]+f[k+1][j]+s[j]-s[i-1]-a[k])
						f[i][j]=f[i][k-1]+f[k+1][j]+s[j]-s[i-1]-a[k],p[i][j]=k;
		cout<<f[1][n]<<endl;
//		for(int i=1;i<=n;i++,cout<
//			for(int j=1;j<=n;j++,cout<<' ')
//				cout<
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

因为贡献函数是一个三元函数，所以不知道怎么样满足四边形不等式，所以主要讲究一个倒推。

证明状态函数满足四边形不等式：
设$p_{i,j+1}=x,p_{i+1,j}=y$，则：
{ f i , j ≤ f i , x − 1 + f x + 1 , j + w x ( i , j ) f i + 1 , j + 1 ≤ f i + 1 , y − 1 + f y + 1 , j + 1 + w y ( i + 1 , j + 1 ) f i , x − 1 + f x + 1 , j + 1 + w x ( i , j + 1 ) = f i , j + 1 f i + 1 , y − 1 + g y + 1 , j + w y ( i + 1 , j ) = f i + 1 , j \left\{

\right. ⎩ ⎨ ⎧​fi,j​≤fi,x−1​+fx+1,j​+wx​(i,j)fi+1,j+1​≤fi+1,y−1​+fy+1,j+1​+wy​(i+1,j+1)fi,x−1​+fx+1,j+1​+wx​(i,j+1)=fi,j+1​fi+1,y−1​+gy+1,j​+wy​(i+1,j)=fi+1,j​​
加起来：
$f_{i,j}+f_{i+1,j+1}+f_{x+1,j+1}+g_{y+1,j}+w_x(i,j+1)+w_y(i+1,j)\le f_{i,j+1}+f_{i+1,j}+f_{x+1,j}+f_{y+1,j+1}+w_x(i,j)+w_y(i+1,j+1)$
我们希望把贡献函数约掉，因此希望有这样一个不等式：
$w_x(i,j)+w_y(i+1,j+1)\le w_x(i,j+1)+w_y(i+1,j)$
这恰为贡献函数的四边形不等式，带入贡献函数的公式会发现显然成立。
剩下的部分就和石子合并的证明一样了，因此状态函数显然满足四边形不等式。

同理，证明决策单调性的部分也和石子合并一模一样，不写了。

所以我们会发现，同一类转移方程能否四边形不等式优化仅仅和$w$是否满足四边形不等式相关。

后记

于是皆大欢喜。