postoffice.java

PKU中一些数据结构基本算法题的java实现

package PKU.DP;
import java.util.*;

/**
 * ID:1160
 * 动态规划
 * Cost[j,i]表示安排前i个邮局给前j个村庄使用
 * D[i,j]表示在第i个到第j个村庄中建立一个邮局得到的最短距离总和。
 * D[a,b]可以利用关系式d[a,a]=0, D[a,b]=D[a,b-1]+x[b]-x[(a+b)/2]表示
 * @author yhm
 *
 */
public class PostOffice {

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int n, m;
		n = cin.nextInt();
		m = cin.nextInt();
		int[] x = new int[n + 1];
		int[][] d = new int[n + 2][n + 2];
		int[][] cost = new int[n + 2][n + 2];
		for (int i = 1; i <= n; i++)
			x[i] = cin.nextInt();
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i >= j)
					d[i][j] = 0;
				else
					d[i][j] = d[i][j - 1] + x[j] - x[(i + j) / 2];
			}
		}
		for (int i = 1; i <= n; i++)
			cost[i][1] = d[1][i];
		for (int i = 2; i <= m; i++) {
			for (int j = i + 1; j <= n; j++) {
				int tmp = Integer.MAX_VALUE;
				for (int k = i - 1; k <= j; k++) {
					if (tmp > cost[k][i - 1] + d[k + 1][j])
						tmp = cost[k][i - 1] + d[k + 1][j]; // Cost[n,m] = min{Cost[i,m-1]+D[i+1,n]}，i=m-1,m,…,n-1。
				}
				cost[j][i] = tmp;
			}
		}
		System.out.println(cost[n][m]);
	}

}