题解 P4767 【[IOI2000]邮局】
SIGSEGV
2018-08-27 11:09:19
四边形不等式.......了解一下？
对于这种要枚举i,j,k,时间复杂度为O(n^3)的dp，使用mk[i][j]记录下k的值，会发现mk[i-1][j] <= k <= mk[i][j+1] （证明[在此](https://blog.csdn.net/u014800748/article/details/45750737)）
本题正常的DP方程很容易想到:dp[i][j]表示前j个村庄中建了i个村庄距离总和的最小值。
我们可以利用数学证明：在i~j之间建立邮局的位置选在中间一定最优，因此计算出在i~j之间建立邮局的最优值w[i][j]，方程便可得出:
### dp[i][j] = max{dp[i][k] + w[k+1][j]}
时间复杂度O(N^3)，优化后为O(N^2)
上代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,m,a[3005],mk[3005][3005];
long long dp[305][3005],w[3005][3005];
int main ()
{
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
sort(a + 1,a + n + 1);//先按坐标排序
for (int i = 1;i <= n;i++)
for (int j = i + 1;j <= n;j++)
w[i][j] = w[i][j - 1] + a[j] - a[(i + j) / 2];//计算w[i][j]的值
for (int i = 1;i <= n;i++) dp[1][i] = w[1][i],mk[1][i] = 0;//初始化
for (int i = 2;i <= m;i++)
{
mk[i][n + 1] = n;//这个值没有计算出来，因此预处理为n
for (int j = n;j > i;j--) //因为在枚举k的时候需要mk[i][j+1]的值，因此倒序枚举j
{
dp[i][j] = 1ll << 60;
for (int k = mk[i - 1][j];k <= mk[i][j + 1];k++)
if (dp[i][j] > dp[i - 1][k] + w[k + 1][j])
dp[i][j] = dp[i - 1][k] + w[k + 1][j],mk[i][j] = k;//更新mk[i][j]
}
}
printf("%lld",dp[m][n]);
return 0;
}
```