题目描述
高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。
邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。
你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。
对于 \(40\%\) 的数据，\(V \leq 300\)。
对于 \(100\%\) 的数据，\(1 \leq P \leq 300\)，\(P \leq V \leq 3000\)，$1 \leq $ 村庄位置 \(\leq 10000\)。
思路点拨
我们从40分做起，这很好像，是子序列提取的模型，我们很容易设出状态并且转移。我们令 \(f_{i,j}\) 表示目前到村庄 \(i\) ，建立的 \(j\) 个基站（\(j\) 是基站）的最小消耗。转移就是枚举上一个基站的位置。
\[f_{i,j}=\min_{mid=0}^{i-1} {f_{mid,j-1}+w_{mid+1,i-1}} \]其中 \(w_{l,r}\) 表示 \(l-1\) 和 \(r+1\) 村庄是基站，那么在 \([l,r]\) 之间的村庄会产生多少消耗。这个东西暴力是 \(O(n^3)\) 的，但是我想到了两种时间复杂度更优秀的做法可以求出它。第一种就是二分法，对于一个区间 \([l,r]\) ,如果我们可以找到最小一个点 \(i\) ,是的 \(i\) 村庄到左边的基站的距离相较于 \(i\) 到右边的基站的距离更远，那么答案无非就是如下：
- \([l,i-1]\) 走向左边的基站，其余走向右边的基站
这样有超时的风险。我们发现，对于同一个 \(l\) ,当 \(r\) 不断变大的时候，我们所说的 \(i\) 有单调性， 所以可以扫一遍就可以了。这个是利用了 \(w\) 的单调性。给出预处理代码：
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
sort(a+1,a+n+1);
for(int l=2;l<n;l++){
int id=l;
for(int r=l;r<n;r++){
while(a[id]-a[l-1]<=a[r+1]-a[id]) id++;
//id肯定会到右边去
w[l][r]=(sum[id-1]-sum[l-1])-(id-l)*a[l-1]+(r-id+1)*a[r+1]-(sum[r]-sum[id-1]);
}
}
我们接下来就不好优化了。但是这个dp是二维的，求得是最小值，我们不妨对 \(w\) 数组打表看看是否满足四边形不等式和区间包含单调性，答案是满足的。具体证明应该十分复杂，但是在考场上一般使用打表法。我们可以利用它优化到 \(O(VP)\) 。代码实现简单，但是边界得要求比较严格，给出如下参考代码：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int MAXN=3e3+10;
int n,m,a[MAXN],sum[MAXN];
int w[MAXN][MAXN];
int pos[MAXN][MAXN],f[MAXN][MAXN];
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
sort(a+1,a+n+1);
for(int l=2;l<n;l++){
int id=l;
for(int r=l;r<n;r++){
while(a[id]-a[l-1]<=a[r+1]-a[id]) id++;
//id肯定会到右边去
w[l][r]=(sum[id-1]-sum[l-1])-(id-l)*a[l-1]+(r-id+1)*a[r+1]-(sum[r]-sum[id-1]);
}
}
for(int l=1;l<=n;l++)
w[l+1][l]=0;
for(int i=0;i<MAXN;i++)
for(int j=0;j<MAXN;j++)
f[i][j]=1e9;
for(int i=1;i<=n;i++){
f[i][1]=a[i]*(i-1)-sum[i-1];
pos[i][1]=1;
}
for(int j=2;j<=m;j++){
f[j][j]=0;
pos[j][j]=j;
pos[n+1][j]=n;
for(int i=n;i>j;i--){
for(int k=pos[i][j-1];k<=pos[i+1][j];k++)
if(f[i][j]>f[k][j-1]+w[k+1][i-1]){
f[i][j]=f[k][j-1]+w[k+1][i-1];
pos[i][j]=k;
}
}
}
int ans=1e9;
for(int i=m;i<=n;i++)
ans=min(ans,f[i][m]+sum[n]-sum[i]-(n-i)*a[i]);
cout<<ans;
return 0;
}