HDUOJ---2546 饭卡

饭卡

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7194    Accepted Submission(s): 2439

Problem Description

电子科大本部食堂的饭卡有一种很诡异的设计,即在购买之前判断余额。如果购买一个商品之前,卡上的剩余金额大于或等于5元,就一定可以购买成功(即使购买后卡上余额为负),否则无法购买(即使金额足够)。所以大家都希望尽量使卡上的余额最少。 某天,食堂中有n种菜出售,每种菜可购买一次。已知每种菜的价格以及卡上的余额,问最少可使卡上的余额为多少。

Input

多组数据。对于每组数据: 第一行为正整数n,表示菜的数量。n<=1000。 第二行包括n个正整数,表示每种菜的价格。价格不超过50。 第三行包括一个正整数m,表示卡上的余额。m<=1000。 n=0表示数据结束。

Output

对于每组输入,输出一行,包含一个整数,表示卡上可能的最小余额。

Sample Input

1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0

Sample Output

-45 32

Source

http://acm.hdu.edu.cn/showproblem.php?pid=2546

Recommend

lcy

背包问题: 代码:

 1 #include<iostream>
 2 #include<vector>
 3 #include<cstring>
 4 #define maxn 1005
 5 using namespace std;
 6 int dp[maxn],flag;
 7 int max(int a,int b)
 8 {
 9     return a>b?a:b;
10 }
11 void zeroonepack(int cost ,int total)
12 {
13     for(int i=total;i>=cost;i--)
14     {
15         dp[i]=max(dp[i],dp[i-cost]+cost);
16     }
17 }
18 
19 int main()
20 {
21    int n,m,i;
22    while(cin>>n,n)
23    {
24        memset(dp,0,sizeof dp);
25        vector<int>arr(n);
26    for(i=0;i<n;i++)
27    {
28        cin>>arr[i];
29        if(i==0||arr[flag]<arr[i])         //找出最贵的那道菜...
30            flag=i;
31    }
32    cin>>m;
33    if(m<5)
34    {
35        cout<<m<<endl;
36        continue;
37    }
38    m-=5;                         //预留5元,用剩下的钱去买最多的菜
39    for(i=0;i<n;i++)
40    {
41        if(flag==i)  continue;    //那道最贵的菜,就不需要比较了!!,最后定然是要吃的
42        zeroonepack(arr[i],m);
43    }
44 
45    cout<<m+5-arr[flag]-dp[m]<<endl;
46    }
47    return 0;
48 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏黑白安全

MicroPython开发实例之自制小型家庭气象站

众所周知,iPhone6/6Plus内置气压传感器,不过大家对于气压传感器还是很陌生。跟字面的意思一样,气压传感器就是用来测量气压的,但测量气压对于普通的手机用...

27910
来自专栏圆方圆学院精选

【戴嘉乐 IPFS】基于IPFS和GeoHash构建具有地理位置价值服务的DDApp(理论篇)

打造地理位置信息与区块链的关系对象模型,建立一套 人->位置->真实世界->传递信任->价值转移->位置->人 的生态模型,实现用区块链来索引真实世界的愿景。

16310
来自专栏Python与爬虫

[资源分享]计算机科学速成课

推荐 程序员的你一定要看,不是程序员的也可以看看,我已经安利刚中考完的我妹妹看了(培养程序媛...)

26230
来自专栏数据派THU

手把手教你用R处理常见的数据清洗问题(附步骤解析、R语言代码)

R是进行运算、清洗、汇总及生成概率统计等数据处理的一个绝佳选择。此外,由于它独立于平台、短期内不会消失,所以生成的程序可以在任何地方运行。并且,它具备非常棒的辅...

59430
来自专栏小樱的经验随笔

元胞自动机实现多数分类算法

元胞自动机(Cellular automaton) 元胞自动机是由元胞组成的网格,每个元胞都根据邻域的状态来选择开或关。所有的元胞都遵循同样的规则,也称为元胞的...

34850
来自专栏ml

HDUOJ----2063过山车

过山车 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

33860
来自专栏Crossin的编程教室

【每周一坑】双色球选号器

说到做到,每周一坑 没有跳票,今天又来了! 我反复说,学会语法只是编程的开始,不断地写代码才是提升技能的必经之路。所以这个栏目我们肯定是要做下去的,哪怕它的阅读...

33750
来自专栏智慧教育

比起WE大会“救命的AI”,这个AI已经悄悄进入人们的学习中

“未来人工智能要进一步发展的话,就需从脑科学得到启发,包括机器学习过程,怎么从脑启发的这个概念来设计新的计算模式,新的类似人脑的神经元结构的器件、芯片,甚至是机...

36140
来自专栏移动开发面面观

OpenGL ES——打光

15250
来自专栏ThoughtWorks

TW洞见 | 成为好QA的5项黄金原则

你知道有什么会让你义无反顾去做,即使工作本身并没什么意思吗?你知道当所有的测试都失败,有人不停地问你到底哪出错了的时候,什么能让你内心仍然很坚强吗? 好吧,我...

376100

扫码关注云+社区

领取腾讯云代金券