洛谷P4767 [IOI2000]邮局（决策单调DP，四边形不等式优化）

题面链接：P4767 [IOI2000]邮局

最近的这些有关数学的真的是做的我头大，但不得不说决策$dp$真的很好用，这里用到了四边形不等式优化，理解的还不是很深，写一篇题解来记录一下。
在本题中我们用$dp[i][j]$前$i$个点放$j$个快递站时，前$i$个点的最小距离,用$w[i][j]$表示区间$[i,j]$放一个快递站时，$[i,j]$内点到快递站的最小距离，显然可以列出状态转移方程:$dp[i][j]={\sum }_{k=0}^{i}dp[k][j-1]+w[k+1][i]$,$w$可以预处理处理，但需要枚举k导致三层循环，很显然复杂度并不能满足我们的要求，此时我们就需要使用四边形不等式优化了，首先我们需要知道，如果某二元函数$w$满足：
$w(i,j)+w(i+1,j+1)<w(i+1,j)+w(i,j+1)$
则称其满足四边形不等式，显然$w$满足上述关系，此时我们需要用到四边形不等式的两个性质
1：

在本题中，因为$w$满足四边形不等式，而$dp[i][j]={\sum }_{k=0}^{i}dp[k][j-1]+w[k+1][i]$，所以dp也满足四边形不等式，若用数组$s[i][j]$储存$dp[i][j]$的最优转移点，那么我们可以利用定理2得知， $s[i][j-1]\le s[i][j]\le s[i+1][j]$,这样我们就使得复杂度成功降低一维。

注意： 因为$s[i][j-1]\le s[i][j]\le s[i+1][j]$，所以需要倒着枚举i

细节见代码及注释：

int dp[3010][3010];//前i个点放j个快递站时，前i个点的最小距离
int w[3010][3010];//区间[i,j]放一个快递站时，[i,j]内点的最小距离
int s[3010][3010];//dp[i][j]的最优转移点
int v[3010];
int n,m;
void init(){//预处理w
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			w[i][j]=w[i][j-1]+v[j]-v[(i+j)/2];//邮局肯定是放中间最好
		}
	}
}
int main(){
/*cout<<setiosflags(ios::fixed)<<setprecision(8)<<ans<<endl;//输出ans（float）格式控制为8位小数（不含整数部分）*/
/*cout<<setprecision(8)<<ans<<endl;//输出ans（float）格式控制为8位小数（含整数部分）*/
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//同步流
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>v[i];
	}
	init();
	memset(dp,inf,sizeof(dp));//初始化，为下面做准备
	dp[0][0]=0;
	for(int j=1;j<=m;j++){
		s[n+1][j]=n;//一会会用，所以提前赋好值
		for(int i=n;i>=1;i--){//因为dp[i][j]的最优转移点s[i][j-1]<=k<=s[i+1][j]，所以倒序
			int min=inf,mp;
			for(int k=s[i][j-1];k<=s[i+1][j];k++){//查找转移点
				if(dp[k][j-1]+w[k+1][i]<min){
					min=dp[k][j-1]+w[k+1][i];
					mp=k;
				}
			}
			s[i][j]=mp;//更新
			dp[i][j]=min;
		}
	}
	cout<<dp[n][m]<<endl;
	return 0;
}
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
31
32
33
34
35
36
37
38
39
40