[IOI2000]邮局
原题地址
解法
一眼看上去并不好想，因为无法确定村庄距哪个邮局最近。
考虑 DP，在 DP 中可以忽略这个不定量的影响。
设 dp[i][k] 表示前 i 个村庄已经放置了 k 个邮局的最短长度
不难想转移方程：\(dp[i][k] = \min{(dp[j][k-1] + w[j + 1][i]}),j \in [0,i)\)。
其中 w(a,b) 表示村庄 (a,b) 间的距离
可以用预处理达到 \(O(P * V^2)\)，无法 AC。
观察发现，w(a,b) 满足四边形不等式，故 dp(a,b) 也满足四边形不等式
(具体证明我不会，看这里证明)
用决策单调性优化一下就行了，时间复杂度 \(O(P*V)\)
点击查看代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 3e3 + 5;
int d[maxn][maxn],a[maxn],n,m,dp[maxn][maxn],w[maxn][maxn];
int main() {
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;++ i)scanf("%d",&a[i]),w[i][i] = 0;
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 >> 1];
}
}
memset(dp , 0x3f , sizeof(dp));
dp[0][0] = 0;
for(int k = 1;k <= m;++ k) {
d[n + 1][k] = n;
for(int i = n;i;-- i) {
for(int j = d[i][k - 1];j <= d[i + 1][k];++ j) {
if(dp[i][k] > dp[j][k - 1] + w[j + 1][i]) {
dp[i][k] = dp[j][k - 1] + w[j + 1][i];
d[i][k] = j;
}
}
}
}
printf("%d",dp[n][m]);
return 0;
}