問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1160思路:
事先知道這是動(dòng)態(tài)規(guī)劃的題，于是就拼命往這方面想，想啊想啊想啊想，終于靈感一現(xiàn):
可以用f[i][j]表示到第i個(gè)村鎮(zhèn)為止，建造j個(gè)郵局所需要的最小距離
心中竊喜，感覺應(yīng)該挺靠譜，于是繼續(xù)深入，直覺告訴我f[i][j]與f[i-1][j], f[i-1][j-1]應(yīng)該有關(guān)系，貌似成了第i個(gè)村鎮(zhèn)建不建郵局的子問題，繼續(xù)苦思冥想，結(jié)果卻還是想不出來。
無奈，還是看別人的思路吧:
用f[i][j]表示前i個(gè)郵局建在前j個(gè)村鎮(zhèn)所需要的最小距離(貌似，跟我之前想的剛好相反)
f[i][j] = min( f[i-1][k] + cost[k+1][j], i-1<=k<=j-1)，cost[i][j]表示在村鎮(zhèn)i與j之間建造一個(gè)post office的最小距離(人家說顯然在中點(diǎn))
艾，差之毫厘，謬以千里，如何有效地表示和分析最優(yōu)子結(jié)構(gòu)是關(guān)鍵：一個(gè)問題的解，如何通過其子問題來表示和求解
代碼:
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 }