HDU 1421 搬寝室

这题是动态规划。

状态设计：很经典的设计dp[i][j]表示从i个物品中选择j个物品来搬运的最小劳累度，很自然的想到答案便是dp[n][k]。

转移方程：因为疲劳度是关于两个物品的，转移的条件就是i选和不选，假设i不选，那么就是前i-1个选j对，也就是dp[i][j]=dp[i-1][j].假设第i个选，那么这个一定是和前一个组成一对的，为什么？因为这个时候数组是排好序的，相邻的两个数据相差才是最小的，这里是一种贪心的思想。dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));

边界条件：从0个物品中搬运0件就不累，dp[0][0]=0;

#include<bits/stdc++.h>
using namespace std;
const int N=2010,inf=0x3fffffff;
int n,k,a[N],dp[N][N];
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+1+n);
        dp[0][0]=0;
        for(int i=0;i<=n;i++)
            for(int j=1;j<=k;j++)
                dp[i][j]=inf;
        for(int i=2;i<=n;i++)
            for(int j=1;j<=k;j++)
                dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));
        printf("%d\n",dp[n][k]);
    }
    return 0;
}