HDU-1421

4746 단어 HDU
/*

a<b<c<d

    :(a-b)^2+(c-d)^2 < (a-c)^2+(b-d)^2

        ,            



dp[i][j]  i     j        ,w[i]   i      

   :

    i==j*2

        dp[i][j] = dp[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1]);

    i>j*2

        dp[i][j] = min(dp[i-1][j],dp[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1]));



2 1

1 3





4

*/

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cmath>

int dp[2005][1005];

 int w[2005];

using namespace std;

int main()

{

    int n,k;

    while(scanf("%d %d",&n,&k)!=EOF)

    {

        for(int i=1;i<=n;i++)

            scanf("%d",&w[i]);

        w[0] = 0;

        sort(w+1,w+n+1);

        for(int i=0;i<2005;i++)

        {

             dp[i][0] = 0;

        }

        for(int j=0;j<1005;j++)

        {

            dp[0][j] = 0;

            dp[1][j] = 0;

        }

        for(int i=2;i<=n;i++)

            for(int j=1;2*j<=i;j++)

        {

           if(i==j*2)

                dp[i][j] = dp[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1]);

            else if(i>j*2)

                dp[i][j] = min(dp[i-1][j],dp[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1]));

        }

        printf("%d
",dp[n][k]); } }

좋은 웹페이지 즐겨찾기