hdu 1421——寝室を運ぶ

寝室を運ぶ.
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 18400    Accepted Submission(s): 6227
Problem Description
2006年7月9日、その日xhdは仕方なく27号棟から3号棟に引っ越しなければならなかった.10号は閉鎖されるからだ.寝室のn件の品物を見て、xhdはぼんやりし始めた.nは2000未満の整数で、本当に多すぎるので、xhdは勝手に2*k件を運んで行けばいいと決めた.しかし、やはり疲れてしまう.2*kも小さくないのでn以下の整数である.幸いなことにxhdは長年の持ち物の経験から左右の手のものの重量差の二乗に比例することが分かった.例えばxhdは左手に重量3のものを持ち,右手に重量6のものを持ち,彼の今回の疲労度は(6-3)^2=9.今かわいそうなxhdはこの2*k件の荷物を運んだ後の最良の状態がどのようなものか(つまり最低の疲労度)を知りたいので、教えてください.
 
Input
各入力データは2行あり、1行目は2個の数n,k(2<=2*k<=n<2000)である、2行目はn個の整数がそれぞれn個の物品の重量(重量は2^15未満の正の整数)を表す.
 
Output
各入力データのセットに対応する出力データは、彼の最低疲労度を示す1行のみである.
 
Sample Input

   
   
   
   

    
    
    
    2 1
1 3
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    4
   
   
   
   

 
Author
xhd
 
Source
ACM夏休み合宿チーム練習試合(二)
 
Recommend
lcy   |   We have carefully selected several similar problems for you:   1058  1257  2084  2571  1978 
 
並べ替え後、隣接する数の二乗差は一定最小とし、dp[i][j]として前i個数選択j対の場合に生じる最低疲労度を表す

#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2010;

int dp[N][1010];
int th[N];

int main()
{
	int n, k;
	while (~scanf("%d%d", &n, &k))
	{
		memset (dp, 0, sizeof(dp));
		for (int i = 1; i <= n; ++i)
		{
			scanf("%d", &th[i]);
		}
		sort (th + 1, th + n + 1);
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 1; 2 * j <= i; ++j)
			{
				if (i == 2 * j)
				{
					dp[i][j] = dp[i - 2][j - 1] + (th[i] - th[i - 1]) * (th[i] - th[i - 1]);
				}
				else if (i > 2 * j)
				{
					dp[i][j] = min(dp[i - 1][j], dp[i - 2][j - 1] + (th[i] - th[i - 1]) * (th[i] - th[i - 1]));
				}
			}
		}
		printf("%d
", dp[n][k]);
	}
	return 0;
}