问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1160思路:
事先知道这是动态规划的题，于是就拼命往这方面想，想啊想啊想啊想，终于灵感一现:
可以用f[i][j]表示到第i个村镇为止，建造j个邮局所需要的最小距离
心中窃喜，感觉应该挺靠谱，于是继续深入，直觉告诉我f[i][j]与f[i-1][j], f[i-1][j-1]应该有关系，貌似成了第i个村镇建不建邮局的子问题，继续苦思冥想，结果却还是想不出来。
无奈，还是看别人的思路吧:
用f[i][j]表示前i个邮局建在前j个村镇所需要的最小距离(貌似，跟我之前想的刚好相反)
f[i][j] = min( f[i-1][k] + cost[k+1][j], i-1<=k<=j-1)，cost[i][j]表示在村镇i与j之间建造一个post office的最小距离(人家说显然在中点)
艾，差之毫厘，谬以千里，如何有效地表示和分析最优子结构是关键：一个问题的解，如何通过其子问题来表示和求解
代码:
1 /* 752K 79MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_V 301
6 #define MAX_P 31
7 #define INF 0x7FFFFFFF
8 int v, p;
9 int pos[MAX_V];
10 int cost[MAX_V][MAX_V];
11 int table[MAX_P][MAX_V];
12
13 void
14 init()
15 {
16 int i, j, k, mid, diff;
17 for(i=1; i<=v; i++) {
18 for(j=i; j<=v; j++) {
19 diff = 0;
20 mid = (i+j)/2;
21 for(k=i; k<=j; k++)
22 diff += ((pos[k]>pos[mid])?(pos[k]-pos[mid]):(pos[mid]-pos[k]));
23 cost[i][j] = cost[j][i] = diff;
24 }
25 }
26 }
27
28 int
29 dp()
30 {
31 int i, j, k, min, tmp;
32 memset(table, 0, sizeof(table));
33 for(j=1; j<=v; j++)
34 table[1][j] = cost[1][j];
35 for(i=2; i<=p; i++) {
36 for(j=i+1; j<=v; j++) {
37 min = INF;
38 for(k=i-1; k<=j-1; k++) {
39 tmp = table[i-1][k] + cost[k+1][j];
40 min = tmp<min ? tmp : min;
41 }
42 table[i][j] = min;
43 }
44 }
45 return table[p][v];
46 }
47
48 int
49 main(int argc, char **argv)
50 {
51 int i;
52 while(scanf("%d %d", &v, &p)!=EOF) {
53 for(i=1; i<=v; i++)
54 scanf("%d", pos+i);
55 init();
56 printf("%d\n", dp());
57 }
58 }