搬寝室

2 1
1 3

4

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100000000
#define M 2010
int dp[M][M/2];

int main(){
    int n,k;
    while(cin>>n>>k){
        int i,j;
        int w[M],v[M];
        for(i=1;i<=n;i++)  cin>>w[i];
        sort(w+1,w+n+1);
        for(i=1;i<n;i++)  v[i]=(w[i]-w[i+1])*(w[i]-w[i+1]);

        for(i=0;i<=n;i++){
            for(j=0;j<=k;j++)
                dp[i][j]=N;
            dp[i][0]=0;
        }

        for(i=2;i<=n;i++)
            for(j=1;2*j<=i;j++)
            dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+v[i-1]);
        cout<<dp[n][k]<<endl;
    }
    return 0;
}

hdu 1421 搬寝室 DP

原文：http://blog.csdn.net/hyccfy/article/details/42875535