HDU1421(搬寝室)

题目入口

我还是太菜，被自己的思维所束缚，一直在想选哪些物品进行组合才能使得这个疲劳值最小。想不出来甚至不知道怎么对这个题的状态进行定义，更别提写出dp转移方程。

思路

正确姿势不仅仅是动态规划，首先要对所有物品重量进行一个排序，因为差值越小疲劳值越小。所以按照从小到大进行排序，相邻的两件物品的差值一定是最小的，也是最合适的。然后在对这些物品进行动态规划。

状态定义：dp[i][j]，从前i件物品中选出j组所获得的最小疲劳值，那么对于第i件物品有两种状态：
1. 第i件物品不选，那么就是从dp[i-1][j]中获得的最小疲劳值
2. 第i件物品选，那么第i件物品必定要和第i-1件物品一起选，那么就是从前i-2件物品中选出j-1组再加上第i件物品和第i-1件物品组成j组。dp[i-2][j-1] + (s[i]-s[i-1])*(s[i]-s[i-1])。

边界状态：前i件物品选出0组所获得的最小疲劳值是0，那么dp[i][0] = 0 (0 <= i <= n)。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2005;
const int inf = 1<<30;
int dp[maxn][maxn];
int s[maxn];
void solve(int n,int k)
{
    for(int i = 0;i <= n;i++){
        for(int j = 1;j <= k;j++){
            dp[i][j] = inf+5;
        }    
        dp[i][0] = 0;				//前i件物品选出0组所得的最小疲劳值是0;
    }    
    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]+(s[i]-s[i-1])*(s[i]-s[i-1]));
        }
    }
    cout << dp[n][k] << endl;
}
int main()
{
    int n,k;
    while(cin>>n>>k){
        for(int i = 1;i <= n;i++){
            cin >> s[i];
        }
        sort(s+1,s+n+1);			//排序
        solve(n,k);
    }
    return 0;
}

mark~