POJ1160, post office。动态规划的经典题目。呃，又是经典题目，DP部分的经典题目怎就这么多。木有办法，事实就这样。
求：在村庄内建邮局，要使村庄到邮局的距离和最小。
设有m个村庄，分别为 V1 V2 V3 … Vm， 要建n个邮局，分别为P1 P2 P3 … Pn。
在DP的问题中，经常有从m个物体中选n个物体的情况，本题显然也属于这种情况。一般可以这样考虑：假设已经选了1个，那么就成了在m-1个中选n-1个的问题了。
对于此题，也可以考虑先建一个邮局。建在哪里呢？不妨设，该邮局建在Vk+1..Vm之间的某个村庄里，而且规定Vk+1..Vm之间再不允许建立其他邮局了。因此，剩下的n-1个邮局必然出现在V1..Vk之间的村庄内，这样问题就转换成：在前k个村庄里选n-1个邮局的问题。
设dp( m,n )表示在V1…Vm之间建立n个邮局时的最短距离。
L( i, j )表示在Vi…Vj之间建立一个邮局的最短距离。
状态转换方程：
dp( m,n ) = Min( dp( k,n-1 ) + L( k+1,m ) ), 其中：1 <= k<m
编程实现：没啥说的，具体看代码。
代码如下
public class POJ1160 { public static int V_MAX = 10; public static int P_MAX = 3; public static int INF = 999999999; // 村庄数 private static int vNum = 10; // 邮局数 private static int pNum = 4; // 村庄坐标 private static int vPos[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // d[i][j]表示在村庄i和村庄j之间建1个Post office的最小距离和 private static int d[][] = new int[vNum][vNum];; // dp[i][j]表示在村庄1和村庄i之间建j个Post office的最小距离和 private static int dp[][] = new int[vNum][pNum];; public static void main(String[] args) { Solve(); System.out.println("-------------dp------------------"); for (int i = 1; i < vNum; i++) { for (int j = 1; j < pNum; j++) { System.out.print(dp[i][j] + " "); } System.out.println(); } } private static void Solve() { // 利用DP，计算d[i][j]的值 for (int i = 1; i < vNum; i++) { for (int j = i + 1; j < vNum; j++) { d[i][j] = d[i][j] + (vPos[j] - vPos[(i + j) / 2]); } } System.out.println("-------------d------------------"); for (int i = 1; i < vNum; i++) { for (int j = 1; j < vNum; j++) { System.out.print(d[i][j] + " "); } System.out.println(); } // dp[i][j]表示在村庄1和村庄i之间建j个Post office的最小距离和 for (int i = 1; i < vNum; i++) { dp[i][0] = Integer.MAX_VALUE; } for (int i = 1; i < vNum; i++) { for (int j = 1; j < pNum && j <= i; j++) { int min = INF; for (int k = j - 1; k < i; k++) { if (dp[k][j - 1] + d[k + 1][i] < min) { min = dp[k][j - 1] + d[k + 1][i]; } } dp[i][j] = min; } } System.out.println(dp[vNum - 1][pNum - 1]); } }
