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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| #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); for (int i=0; i<=n; ++i) dp[i][0] = 0; 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; }
|