/* 动态规划。 将n个村庄按坐标递增依次编号为1，2，……，n，各个邮局的坐标为a[1..n]， 状态表示描述为：f[i,j]表示在前i个村庄建立j个邮局的最小距离和。所以，f[n,p]即为问题的解， 且状态转移方程和边界条件为： f[j,1]=w[1,j]; f[i,j]=min{f[k,j - 1]+w[k+1,i]}; (i≤j, j – 1≤k≤i) 其中w[i,j]表示在a[i..j]之间建立一个邮局的最小距离和，可以证明，当仅建立一个邮局时， 最优解出现在中位数，于是，我们有： w[i,j]=w[i,j]+|a[k]-a[t]| (1<=i */ 【代码】 #include <stdio.h> #include <string.h> #include <math.h> #define min(a,b) a<b?a:b int main() { int n, m, a[301], f[301][31], i, j , k, w[301][301]; scanf("%d%d", &n, &m); for (i = 1; i <= n; i++) scanf("%d", &a[i]); for (i = 0; i <= n; i++) for (j = 0; j <= m; j++) f[i][j] = 100000; memset(w, 0, sizeof(w)); for (i = 1; i <= n; i++) { for (j = i; j <= n; j++) { for (k = i ; k <= j; k++) w[i][j] += abs(a[k] - a[(i + j) / 2]); } } for (i = 1; i <= n; i++) f[i][1] = w[1][i]; for (j = 2; j <= m; j++) { for (i = j; i <= n; i++) { for (k = j - 1; k < i; k++) { f[i][j] = min(f[i][j], f[k][j - 1] + w[k + 1][i]); } } } printf("%d\n", f[n][m]); return 0; }
查看更多关于php邮局问题 vijos1242(和以前的pku上的应该是一样的的详细内容...