HDOJ1421搬卧房（动态规划）

HDOJ1421搬寝室（动态规划）

分析：题目意思应该很清楚，想到首先需把所有的东西按重量排下序，然后再想办法。数据不大但涉及很大量的重复问题，应该想到用动态规划思想。i表示要搬东西的数量，j表示要搬的次数，状态方程：dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(num[i-2]-num[i-1])^2

代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
int num[2010];
int dp[2005][2005];//可改为滚动数组做，dp[3][2005],这样没超时，就没简化
int main()
{
    int n,m,i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&num[i]);
        sort(num,num+n);
        for(i=0;i<n;i++)
        {
            for(j=1;j<n;j++)
                dp[i][j]=100000000;
            dp[i][0]=0;
        }
        for(i=2;i<=n;i++)
            for(j=1;j<=m,j<=i;j++)
                dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(num[i-1]-num[i-2])*(num[i-1]-num[i-2]));
        printf("%d\n",dp[n][m]);
    }
    return 0;
}