邮局问题 vijos1242(和以前的pku上的应该是一样的.)

发表回复

/*
动态规划。
将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

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

#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;
}