HDU 1421

HDU 1421

• 刚开始的思路: 想到将所有物品重量的差求出来排序然后直接取出前m对最小的

  忽略了 一个差代表2个个物品被取走了,那么其他包含这2个物品的差就应该消失,实现标记很困难

DP思路

• 先将所以重量排个序（那么每个物品的前后2个物品与此物品的差最小,注意到差值和物品重量大小无关）

• 状态dp[i][j]表遍历到到第i件物品, j 代表已经选了j对物品,dp[i][j]代表n件物品取j对的最小疲劳值

  • 选 $dp[i][j] = dp[i-2][j-1]+(num[i]-num[i-1])^2$
  • 不选 $dp[i][j] = dp[i-1][j]$
  • 状态转移: $dp[i][j] = min(dp[i-2][j-1]+(num[i]-num[i-1])^2),dp[i-1][j]$

• 初始化条件: dp[i][0] 一对不取消耗值为0

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2050;

int a[maxn];
int dp[maxn][maxn];
int n,m;

int power(int a,int b) {
    return (a - b)*(a - b);
}
int main() {
    while (scanf("%d%d",&n,&m) != EOF && (n+m)) {
        for (int i=1; i<=n; ++i)
            scanf("%d",&a[i]);
        sort(a+1,a+1+n);
        memset(dp,0x3f,sizeof dp);
        // 无论多少个i 一对没取 必须消耗值必须为0
        for (int i=0; i<=n; ++i) dp[i][0] = 0;
        // 从第2个物品开始dp
        for (int i=2; i<=n; ++i)
            for (int j=1; j*2<=i; ++j)
                dp[i][j] = min(dp[i-1][j],dp[i-2][j-1]+power(a[i],a[i-1]));
        printf("%d\n",dp[n][m]);
    }
    return 0;
}