HDU 1421 搬起居室

/*
状态转移方程：d[i][j] = min(d[i][j - 1], d[i - 1][j - 2] + (A[j] - A[j - 1]) * (A[j] - A[j - 1]))
d[i][j]:表示前j个物品搬运i次最小的疲劳度
*/


#include <iostream>
#include <cmath>
using namespace std;
const int nMax = 2002;
const int INF = 0xfffffff;
int d[nMax][nMax];
int n, k;
int A[nMax];

int fmin(int a, int b)
{
	return a < b ? a : b;
}

int cmp(const void *a, const void *b)
{
	int *pa = (int *) a;
	int *pb = (int *) b;
	return *pa - *pb;
}

int main()
{
	//freopen("e://data.in", "r", stdin);
	while(scanf("%d%d", &n, &k) != EOF)
	{
		int i, j;
		for(i = 0; i < n; ++ i) scanf("%d", &A[i]);
		qsort(A, n, sizeof(A[0]), cmp);
		int min = INF;
		for(i = 0; i <= k; ++ i)//如果遇到不可访问节点，则需要定义为INF
		{
			for(j = 0; j <= n; ++ j)
				d[i][j] = INF;
		}
		for(i = 1; i <= k; ++ i)
		{
			for(j = 2 * i - 1; j < n; ++ j)
			{
				if(i == 1) //这里更好的处理方法是将d[0][]全部定义为0，所以先写主程序，再处理边界
					d[i][j] = fmin(d[i][j - 1], (A[j] - A[j - 1]) * (A[j] - A[j - 1]));
				else
					d[i][j] = fmin(d[i][j - 1], d[i - 1][j - 2] + (A[j] - A[j - 1]) * (A[j] - A[j - 1]));
			}
		}
		printf("%d\n", d[k][n - 1]);
	}
	return 0;
}