学步园

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1421

犯了个超级低级错误本来应该i==2*j的写成  i=2*j.......然后导致无限超时。。。。= =！

对于这题我也是照葫芦画瓢做的。。。

做完然后稍微有点理解了。。。

首先对于n个数如何产生k对最优的解（也就是两数之差的平方）呢？

对于单个的某一个数的最优解一定是除去这个数剩下n-1个数中找到最接近他的那两个数（比它大和比它小的数）。可能只有一个。

然而对于整体就是从中挑选最优、

首先将数组排序。就可以求单个数的左右最优解；

然后动态规划   用f[i][j]  存放前i个数中挑选最优的j组数。

转移方程为  

 
  当i=j*2时,只有一种选择即 Dp[i-2][j-1]+(w[i]-w[i-1])^2

    当i>j*2时,Dp[i][j] = min(Dp[i-1][j],Dp[i-2][j-1]+(w[j]-w[j-1])^2)
   

下面是AC代码：

#include<iostream>
using namespace std;
#define N 2009
int dp[N][N];
int a[N];
int min(int a,int b)
{   return a>b?b:a;  }
int cmp(const void *a,const void *b)
{
	return *(int *)a-*(int *)b;
}
int main()
{
	int n,k;
	int i,j;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		memset(dp,0,sizeof(dp));
		memset(a,-1,sizeof(a));

		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		
		qsort(a+1,n,sizeof(int),cmp);
		
		for(j=1;j<=k;j++)
			for(i=j*2;i<=n;i++)
			{	
				if(i==2*j)
					dp[i][j]=dp[i-2][j-1]+(a[i-1]-a[i])*(a[i-1]-a[i]);
				else
				{
					dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(a[i-1]-a[i])*(a[i-1]-a[i]));
				}
				
			}
			printf("%d\n",dp[n][k]);
			
			
	}
	return 0;
}