dp46上 HDU1421-白红宇的个人博客

dp46上 HDU1421

发布日期：2021-06-29 21:39:39 浏览次数：3 分类：技术文章

本文共 1529 字，大约阅读时间需要 5 分钟。

搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2*k件过去就行了.但还是会很累,因为2*k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)^2 = 9.现在可怜的xhd希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧.

Input

每组输入数据有两行,第一行有两个数n,k(2<=2*k<=n<2000).第二行有n个整数分别表示n件物品的重量(重量是一个小于2^15的正整数).

Output

对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.

Sample Input

2 11 3

Sample Output

分析：首先以dp[n][k]，表示在n件物品只能选取k对的最优解，那么这种状态可以分为以下两种情况。

(1):第n件物品不搬，也就是在前n-1件物品中选取k对，疲劳值为dp[n-1][k]

(2):第n件物品要搬，那么相应的肯定是要搬第n-1件物品的，因为对于排序之后的序列，相邻两个数之差总是最小的。那么对应的就是在n-2件物品中搬k-1对，然后再加上第n-1对物品时的消耗，也就是n-1和n这一对。疲劳值为：

dp[n-2][k-1]+a[n-1]

所以状态转移方程自然就是两种情况取最小值即可；

即：dp[n][k]=min(dp[n-1][k]，dp[n-2][k-1]+a[n-1])；

当然还是要注意边界问题：

当2 * j > i时，即要搬的数量超过了物品总量，这是不可能发生的，因此此时令f[i][j]为无穷大；

当j == 0时，即在一对物品都没搬时，所需疲劳值应该是0，此时令f[i][j] = 0。

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=2005;

const int INF=0x1f1f1f1f;//无穷大

int a[maxn];

int dp[maxn][maxn/2];

int work(int i,int j)//这里是判断边界问题

{

if(j*2>i)//当你选取物品数大于总数时候，这种情况不发生

return INF;

if(j==0)//一件物品都没搬过的时候，疲劳值为0

return 0;

return dp[i][j];

}

int main()

{

int n,k;

while(scanf("%d%d",&n,&k)!=EOF)

{

memset(dp,0,sizeof(dp));

for(int i=1;i<=n;i++)

{

scanf("%d",&a[i]);

}

sort(a+1,a+n+1);

for(int i=1;i<n;i++)//根据题意做一下预处理

{

a[i]=a[i+1]-a[i];

a[i]*=a[i];

}

for(int j=1;j<=k;j++)//枚举对数

{

for(int i=2*j;i<=n;i++)//枚举物品数

{

dp[i][j]=min(work(i-1,j),work(i-2,j-1)+a[i-1]);

}

printf("%d\n",dp[n][k]);

}

return 0;

}

转载地址：https://dh-butterfly.blog.csdn.net/article/details/70161271 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：UESTC 1324线段树

下一篇：dp46上 HDU2084

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章