hdu1421 参考答案

   1 /*
   2 hdu1421 DP
   3 ymc 2008/10/08
   4 题目大意：
   5 给定n个物品，每个物品有重量，
   6 从中选出m对，使得这m对物品重量差的平方和最小。
   7 疲劳度：m对物品重量差的平方和
   8 分析与解题思路
   9 先对n中物品的重量排序
  10 令ans[i][k]表示前i个物品中选k对的最小疲劳度。
  11 1) 则ans[i][k]可能含有第i个物品(这种情况下,第i种物品一定是和
  12 第i-1个物品配对)，
  13 则ans[i][k]=ans[i-2][k-1]+(a[i]-a[i-1])
  14 2) ans[i][k]的k对也可能不含有第i个物品，此时有
  15 ans[i][k]=ans[i-1][k]。(条件2k<=i-1)
  16 状态转移方程
  17 ans[i][k]=min{ans[i-2][k-1]+(a[i]-a[i-1])*(a[i]-a[i-1]),ans[i-1][k]}
  18 */
  19 #include <iostream>
  20 #include <algorithm>
  21 using namespace std;
  22 const int N=2010;
  23 int a[N];
  24 int n,m;
  25 int ans[N][N/2];
  26 void DP()
  27 {
  28     memset(ans,0,sizeof(ans));
  29     sort(a+1,a+n+1);
  30     for(int k=1;k<=m;k++)
  31         for(int i=k+k;i<=n;i++)
  32         {
  33             ans[i][k]=ans[i-2][k-1]+(a[i]-a[i-1])*(a[i]-a[i-1]);
  34             if(i-1>=k+k&&ans[i-1][k]<ans[i][k])
  35                 ans[i][k]=ans[i-1][k];
  36         }
  37 }
  38 int main()
  39 {
  40     while(scanf("%d %d",&n,&m)!=EOF)
  41     {
  42         for(int i=1;i<=n;i++)
  43             scanf("%d",&a[i]);
  44         DP();
  45         printf("%d\n",ans[n][m]);
  46     }
  47 }