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< <
代码:
#includeusing 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年03月22日 22时26分23秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
c语言 无错 但只运行一半,求哈夫曼编码时程序运行到一半就终止了,编译无错...
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
es审计日志_elasticsearch 事务日志translog
2019-04-21
dw1510_超低温种子储存柜
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
babylonjs 设置面板位置_babylonjs 空间坐标转为屏幕坐标
2019-04-21