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]));elsed[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;}