#include<iostream>
#include<algorithm>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int a[2005];
int dp[2005][1005];//从前i个物品中选取j对
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool cmp(int a,int b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
return a < b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int getMin(int a,int b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if(a < b)
return a;
else
return b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int n,k;
while(cin>>n>>k)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int i,j;
for(i = 1;i <= n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cin>>a[i];
}
sort(a+1,a+n+1,cmp);
for(i = 0 ; i <= n ;i++ )//物品
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j = 1;j <= k;j++)//选取的对数
dp[i][j] = 100000000;//一定要足够大
}
for(i = 0;i <= n;i++)
dp[i][0] = 0;
for(i = 2;i <= n;i++ )
for(j = 1;2*j <= i && j <= k;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
dp[i][j] = getMin(dp[i-1][j],dp[i-2][j-1] + (a[i] - a[i-1])*(a[i] - a[i-1]));
}
cout<<dp[n][k]<<endl;
}
return 0;
}