专栏首页mlHDUOJ---2546 饭卡

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 条评论
登录 后参与评论

相关文章

  • 暑假集训之专题----拓扑排序题解

    第一单: Problem A Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/3276...

    Gxjun
  • HDUOJ----湫湫系列故事——减肥记I

    湫湫系列故事——减肥记I Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768...

    Gxjun
  • C++ template的一些高级用法(元编码,可变参数,仿函数,using使用方法,. C++ 智能指针)

    1 .  通用函数可变参数模板      对于有些时候,我们无法确切的知道,函数的参数个数时,而又不想过多的使用所谓的函数重载,那么就可以效仿下面的例子: 1...

    Gxjun
  • P1387 最大正方形

    题目描述 在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形,输出边长。 输入输出格式 输入格式: 输入文件第一行为两个整数n,m(1<=n...

    attack
  • 提示Android屏幕适配方案分析

    Android开发过程中我们常用的尺寸单位有px、dp,还有一种sp一般是用于字体的大小。但是由于px是像素单位,比如我们通常说的手机分辨例如1920*1080...

    用户2356368
  • 暑假集训之专题----拓扑排序题解

    第一单: Problem A Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/3276...

    Gxjun
  • 洛谷P1976 鸡蛋饼

    题目背景 Czyzoiers 都想知道小 x 为什么对鸡蛋饼情有独钟。经过一番逼问,小 x 道出 了实情:因为他喜欢圆。 题目描述 最近小 x 又发现了一个关于...

    attack
  • 蓝桥杯省内模拟赛C++

    问题描述   将LANQIAO中的字母重新排列,可以得到不同的单词,如LANQIAO、AAILNOQ等,注意这7个字母都要被用上,单词不一定有具体的英文意义。...

    用户7727433
  • RMQ问题(线段树算法,ST算法优化)

    RMQ (Range Minimum/Maximum Query)问题是指: 对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A...

    Angel_Kitty
  • hdu1043

    @坤的

扫码关注云+社区

领取腾讯云代金券