hdu-寒冰王座(01背包)
发布日期:2022-02-02 02:58:03 浏览次数:12 分类:技术文章

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

Problem Description
不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.
死亡骑士:"我要买道具!"
地精商人:"我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个."
死亡骑士:"好的,给我一个血瓶."
说完他掏出那张N元的大钞递给地精商人.
地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."
死亡骑士:"......"
死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.
现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.
 
Input
输入数据的第一行是一个整数T(1<=T<=100),代表测试数据的数量.然后是T行测试数据,每个测试数据只包含一个正整数N(1<=N<=10000),N代表死亡骑士手中钞票的面值.
注意:地精商店只有题中描述的三种道具.
 
Output
对于每组测试数据,请你输出死亡骑士最少要浪费多少钱给地精商人作为小费.
 
Sample Input
2900250
 
Sample Output
050
分析:

#include
#include
using namespace std;int main(){ int i,j,k,t,n; int a[3]={150,200,350}; int dp[10005]; cin>>t; while(t--) { cin>>n; memset(dp,0,sizeof(dp)); for(i=0;i<3;i++) { for(j=a[i];j<=n;j++) { dp[j]=max(dp[j],dp[j-a[i]]+a[i]); } } cout<
<
其实此题也可以不用完全背包

代码:

#include
using namespace std;int main(){ int i,j,k,s,n,p; cin>>n; while(n--) { cin>>s; int flag=0; int max=0; for(i=s/350;i>=0&&!flag;i--) { for(j=(s-i*350)/200;j>=0&&!flag;j--) { for(k=(s-j*200-i*350)/150;k>=0&&!flag;k--) { p=i*350+j*200+k*150; if(p>max) { max=p; if(max==s) { flag=1; } } } } } cout<
<

转载地址:https://blog.csdn.net/u010368749/article/details/10026331 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Map 函数
下一篇:hdu——Big Number

发表评论

最新留言

很好
[***.229.124.182]2024年03月22日 22时26分23秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

s2-045 php exp,S2-045-EXP.py --Struts2任意代码执行漏洞 (S2-045,CVE-2017-5638) 2019-04-21
linux sdk 窗口句柄,Venus: 针对Linux平台上,对常用的系统API进行面向对象的封装SDK。... 2019-04-21
c语言程序设计 科学出版社习题答案,C语言程序设计(科学出版社)第4章 课后习题参考答案.doc... 2019-04-21
c语言 无错 但只运行一半,求哈夫曼编码时程序运行到一半就终止了,编译无错... 2019-04-21
deepin linux 2014安装,2014.2版本的Deepin虚拟机安装浅谈(就是深度Linux) 2019-04-21
android 限速工具,Android下载器之限速篇 2019-04-21
html刷新ajax实现原理,AJAX的原理—如何做到异步和局部刷新 2019-04-21
html中列表菜单加文字请选择,html中下拉菜单 2019-04-21
读书郎平板中android,读书郎学生平板电脑怎么用 使用方法详解【图文】 2019-04-21
html5 调用摄像头 支持IE,JS调用本地摄像头拍照(兼容各大浏览器及IE8+) 2019-04-21
rust和gta5哪个吃配置_盘点4款Steam“自由度”很高的游戏,GTA5众所周知,目前最热门... 2019-04-21
es审计日志_elasticsearch 事务日志translog 2019-04-21
dw1510_超低温种子储存柜 2019-04-21
文件未找到mathpage.wll_解决MathPage.wll文件找不到的问题(找了好久的良心之作)... 2019-04-21
java 使用或覆盖了已过时的api_JAVA使用或覆盖了已过时的 API 2019-04-21
java 图片旋转保存_Java 对图片90度旋转 2019-04-21
用java实现文学研究助手_数据结构文学研究助手 C语言代码实现(带源码+解析)... 2019-04-21
java gc的几种方式_GC 的三种基本实现方式 2019-04-21
wget linux java 32_通过wget在Linux上下载Java JDK会显示在许可证页面上 2019-04-21
babylonjs 设置面板位置_babylonjs 空间坐标转为屏幕坐标 2019-04-21