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

 ```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 #include #include #include   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; }```