2780390_ac_1746ms_3456k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main {

	public static int MIN(int a,int b)
	{
		if(a>b)
			return b;
		return a;
	}
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		
		int i, j, k, mid, p, n;
		int pos[] = new int [301];
		int cost[][] = new int [301][301];
		int f[][] = new int [301][301];
		int inf = 100000000;
		
		n = cin.nextInt();
		p = cin.nextInt();
		for (i = 1; i <= n; i++)
			pos[i] = cin.nextInt();
		for (i = 1; i <= n; i++)
		{
			for (j = i; j <= n; j++)
		    {
				cost[i][j] = 0;
		        mid = (i + j) / 2;
		        for (k = i; k <= mid; k++)
		        	cost[i][j] += pos[mid] - pos[k];
		        for (k = mid + 1; k <= j; k++)
		        	cost[i][j] += pos[k] - pos[mid];
		    }
		}
		 for (i = 0; i <= p; i++)
			 for (j = 0; j <= n; j++)
		            f[i][j] = inf;
		 f[0][0] = 0;
		 for (i = 0; i <= p; i++)
			 for (j = 0; j <= n; j++)
				 if (f[i][j] < inf)
				 {
					 for (k = 1; j + k <= n; k++)
		                f[i+1][j+k] = MIN(f[i+1][j+k],f[i][j]+cost[j+1][j+k]);
				 }
		 System.out.println(f[p][n]);
	}
}