题目：搬寝室

典型的DP，状态方程：

dp[k][i]=min(dp[k-1][i-2]+(a[i]-a[i-1])^2,dp[k][i-1]);         dp[k][i] 表示 k 对物品在前 i 个物品的最小值

#include<iostream>
#include<stdio.h>
#include<algorithm>
#define N 2005
using namespace std;
int dp[N/2][N];
int a[N];void Init(int k)
{int i;dp[k][2*k]=0;for(i=2;i<=2*k;i+=2)dp[k][2*k]+=(a[i]-a[i-1])*(a[i]-a[i-1]);
}int work(int n,int m)
{int i,k;sort(a+1,a+n+1);for(k=1;k<=m;k++)  Init(k);for(k=1;k<=m;k++){for(i=2*k+1;i<=n;i++){dp[k][i]=min(dp[k][i-1],dp[k-1][i-2]+(a[i]-a[i-1])*(a[i]-a[i-1]));}}return dp[m][n];
}int main()
{int n,k;while(scanf("%d%d",&n,&k)!=EOF){int i;for(i=1;i<=n;i++)cin>>a[i];int ans=work(n,k);printf("%d\n",ans);}return 0;
}