HDu 1421寝室を運んで寝室を運ぶTime Limit:2000/1000 MS(Java/others)Memory Limit:65536/32768 K(Java/others)

リュックサックと似ていますが、まずsortを1回、それから2階forを循環して、1回巡ります.
寝室を運ぶ.
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 23926    Accepted Submission(s): 8187
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
 
コード:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define min(a,b) a<b?a:b
using namespace std; int a[2010][2010],b[2010]; int f(int j,int i) { if(j<2*i) return 1000000000; if(!i) return 0; return a[j][i]; } int main() { int n,k; while(scanf("%d%d",&n,&k)!=EOF) { int i,j; for(i=1; i<=n; i++)
            scanf("%d",&b[i]);
        sort(b+1,b+n+1); for(i=1; i<n; i++)
            b[i]=(b[i+1]-b[i])*(b[i+1]-b[i]); for(i=1; i<=k; i++) for(j=2*i; j<=n; j++)
                a[j][i]=min(f(j-1,i),f(j-2,i-1)+b[j-1]);
        printf("%d
",a[n][k]); } }