[HDU 1421]搬寝室(富有新意的DP)

题目地址：

题目大意：给出n个物品，要你选出k对物品。使得每对物品之差的平方之和最小。

思路。动态规划求解。首先将物品按重量升序排序，依据贪心思想，每对物品必定是相邻的两个物品，这样重量差的平方才干保证最小。然后DP，用f[i][j]表示前i个物品，选j对的最少代价，这里须要进行一个重要的分类讨论：

(1)假设j*2=i,即前i个物品所实用于配对了，非常明显第j对物品是第i-1号物品和第i号物品，f[i][j]=f[i-2][j-1]+(w[i]-w[i-1])^2

(2)其它情况。前i个物品并没有全然用于配对。能够选择第i个物品不配对。这时f[i][j]=f[i-1][j]。或者第i个物品參与配对，同(1)。第i个物品和第i-1个物品配对，f[i][j]=f[i-2][j-1]+(w[i]-w[i-1])^2

终于的答案就是f[n][k]

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <algorithm>

#define MAXN 2010

using namespace std;

int f[MAXN][MAXN]; //f[i][j]=前i个物品。选j对的最小花费

int w[MAXN];

int min(int a,int b)

{

    if(a<b) return a;

    return b;

}

int main()

{

    int n,k;

    while(scanf("%d%d",&n,&k)!=EOF)

    {

        memset(f,0,sizeof(f));

        w[0]=0;

        for(int i=1;i<=n;i++)

            scanf("%d",&w[i]);

        sort(w+1,w+n+1);

        for(int i=2;i<=n;i++) //前i个物品

            for(int j=1;j*2<=i;j++) //选j对

            {

                if(i!=2*j) f[i][j]=min(f[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1]),f[i-1][j]); //要么第i个物品和第i-1个物品配对。要么留着第i个物品不配对

                else f[i][j]=f[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1]);

            }

        printf("%d\n",f[n][k]);

    }

    return 0;

}