hdu1421 搬寝室--DP
发布日期:2021-10-03 20:31:58
浏览次数:6
分类:技术文章
本文共 1520 字,大约阅读时间需要 5 分钟。
原题链接:
一:原题内容
Problem Description
搬寝室是很累的,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
4
二:分析理解
首先,要怎么搬呢?即每一对要怎么取?如果有abcd四个数,且a<b<c<d,应该是取ab,cd好呢还是ac,bd好?抑或是bc,ad好呢?答案是第一种,因为:
(a-b)^2+(c-d)^2 < (a-c)^2+(b-d)^2 (a-b)^2+(c-d)^2 < (a-d)^2+(b-c)^2 即每对物品都应是重量最为接近的物品,也就是说对n件物品排序后,每对物品都应该是连续的。 数组dp[n][k]来表示在n件物品中搬k对的最佳状态,而达到这一状态的决策可能为: 第n件物品不搬,即在前n - 1件物品中搬k对,那么疲劳值仍为dp[n - 1][k]; 第n件物品要搬,那么根据上面所证,第n - 1件物品也要同时搬,即在前n - 2件物品中搬k - 1对物品,再搬最后一对物品,那么疲劳值为dp[n - 2][k - 1] + (a[n - 1]-a[n])*(a[n - 1]-a[n]),n - 1是因为对数必然比总物品数少1。三:AC代码
#include#include #include #include using namespace std;const int INF = 1 << 30;//傻逼了,int的最大值是2^31-1,不是2^31,哎呦我去int a[2005];int dp[2005][1005];int main(){ int n, k; while (~scanf("%d%d", &n, &k)) { for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a + 1, a + n + 1); for (int j = 1; j <= k; j++) { for (int i = 1; i <= n; i++) { if (j * 2 <= i) dp[i][j] = min(dp[i - 1][j], dp[i - 2][j - 1] + (a[i - 1] - a[i])*(a[i - 1] - a[i])); else dp[i][j] = INF; } } printf("%d\n", dp[n][k]); } return 0;}
转载地址:https://blog.csdn.net/LaoJiu_/article/details/50966065 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月22日 13时16分52秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
浅谈代码覆盖率
2019-04-27
Java代码覆盖率历史发展轨迹
2019-04-27
【防止重复下单】分布式系统接口幂等性实现方案
2019-04-27
一图秒懂开源许可证协议-GPL、BSD、MIT、Mozilla、Apache,LGPL
2019-04-27
websocket 项目启示录
2019-04-27
性能测试
2019-04-27
Java电商系统商品详情页存储方案设计
2019-04-27
Jacoco探针源码解析(0.8.5 版本)
2019-04-27
Java的Instrumentation类原理分析
2019-04-27
"org.jacoco.agent.rt" 在 maven 中找不到
2019-04-27
计算机中的dump到底是什么意思?
2019-04-27
JaCoCo探针策略原理及案例总结
2019-04-27
阿里三面:说说线程封闭与ThreadLocal的关系
2019-04-27
看完让你吊打面试官-@Autowired注解到底怎么实现的?
2019-04-27
MySQL的行锁、表锁、间隙锁详解
2019-04-27
和阿里面试官扯了半小时ArrayBlockingQueue源码
2019-04-27
远离996,PDMan开源免费的国产数据库建模工具!
2019-04-27
现代操作系统的存储器结构
2019-04-27
深度揭秘年薪60W的阿里P7简历制作过程!
2019-04-27
可能是全网最全的SpringBoot启动流程源码分析(基于 2.1.5 版本)
2019-04-27