题意 中文
先把物品重量从小到大排序 d[i][j]表示前i件物品选j对的最小疲劳
那么就有转移方程d[i][j]=min(d[i-1][j],d[i-2][j-1]+(w[i]-w[i-1])^2)
d是初始化为无穷大的 所以i=j*2时 d[i-1][j]是等于无穷大的 所以状态转移方程可以统一为
d[i][j]=min(d[i-1][j],d[i-2][j-1]+(w[i]-w[i-1])^2)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2014;
int w[N], d[N][N / 2], n, k;
int main()
{
while (~scanf ("%d%d", &n, &k))
{
for (int i = 1; i <= n; ++i)
scanf ("%d", &w[i]);
sort (w + 1, w + n + 1);
memset (d, 0x7f, sizeof (d));
for (int i = 0; i <= n; ++i) d[i][0] = 0;
for (int i = 2; i <= n; ++i)
for (int j = 1; j * 2 <= i; ++j)
d[i][j] = min (d[i - 1][j], d[i - 2][j - 1] + (w[i] - w[i - 1]) * (w[i] - w[i - 1]));
printf ("%d\n", d[n][k]);
}
return 0;
}2 1 1 3
4
HDU 1421 搬寝室(DP),布布扣,bubuko.com
原文：http://blog.csdn.net/iooden/article/details/38487887