博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDOJ---1421 搬寝室[DP]
阅读量:5875 次
发布时间:2019-06-19

本文共 1138 字,大约阅读时间需要 3 分钟。

搬寝室

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 8907    Accepted Submission(s): 2996

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 1 1 3
 

 

Sample Output
4
 

 

Author
xhd
 

 

Source
 

 

Recommend
lcy
 
 
 
 
动态方程:dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+fun(i-1,i));        //dp[i][j]表示在取第i件物品前,已经有j对物品被选中
code:
1 #include 
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
12 #include
13 #include
14 #include
15 #include
16 #include
17 #include
18 #include
19 using namespace std;20 21 #define min(a,b) a

 

转载地址:http://hzkix.baihongyu.com/

你可能感兴趣的文章
Centos7.6安装MySQL+Redis(最新版)
查看>>
ListIterator
查看>>
Redis实战之限制操作频率
查看>>
单例模式
查看>>
RxSwift笔记四变换序列
查看>>
前端基础知识复习之CSS
查看>>
Python学习笔记 - 文件和异常
查看>>
使用nodejs crypto模块进行sha1、md5加密
查看>>
18-09-28
查看>>
大数据MongoDB之NoSQL数据库分类(按存储类型分)
查看>>
通过更快,更一致的决策提高生产力和盈利能力
查看>>
[数据库管理]SQL表定义查询与数据字典的导出
查看>>
Android Binder的使用
查看>>
Cocos2dx源码记录(8) CCMaterial, CCTechnique,CCPass
查看>>
springmvc+mybatis+restful+webservice 分布式架构
查看>>
Oracle 面试题总结
查看>>
Flutter RichText支持图片显示和自定义图片效果
查看>>
微软开发人工智能系统 在吃豆人游戏中获满分
查看>>
Mint UI loadmore禁止下拉
查看>>
Vue下拉刷新组件
查看>>