F –
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
SubmitStatus

Description
,xhd.200679,xhd273,10.n,xhd,n2000,,xhd2*k.,2*kn.xhd(,xhd,).xhd3,6,(6-3)^2 = 9.xhd2*k(),.

Input
,n,k(2<=2*k<=n<2000).nn(2^15). Output ,,. Sample Input 2 1 1 3 Sample Output 4

?Download sourceCode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int f[2010][1005];            //long long 
int v[2010], vv[2010];
 
int getF(int x, int y){        //
    if(y * 2 > x)
        return 1000000000;
    else if(y == 0)
        return 0;
    else
        return f[x][y];
}
 
int main(){
    int n, k, i, j;
    while(~scanf("%d %d",&n, &k)){
        for(i = 1; i <= n; i ++){
            scanf("%d", &v[i]);
        }
        sort(v + 1, v + n + 1);
        for(i = 1; i <= n-1; i ++){
            v[i] = v[i+1] - v[i];
            v[i] *= v[i];                //
        }
        memset(f, 0, sizeof(f));
        for(j = 0; j <= k; j ++){  
            for(i = j * 2; i <= n; i ++){
                f[i][j] = min(getF(i-1, j), getF(i-2, j-1) + v[i-1]);
            }
        }
        printf("%d\n",f[n][k]);
    }
    return 0;
}