hdu2546 饭卡 (背包问题)

hdu2546 饭卡 (背包问题)

饭卡

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

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

​​UESTC 6th Programming Contest Online​​

Recommend

lcy   |   We have carefully selected several similar problems for you:   ​​2955​​​  ​​​1203​​​  ​​​2159​​​  ​​​2191​​​  ​​​1114​​

​​Statistic​​ |

​​Submit​​ |

​​Discuss​​ |

​​Note​​

一个背包问题。就是提前需要一个预处理。。找到价格最高的饭菜，花费五元买去它。

然后就编程了n-1个物品,m-5元钱的背包问题。。

#include #include int main(){ int n,m,pri[1005],dp[1005]; while(scanf("%d",&n)&&n) { int max=0,mark; memset(dp,0,sizeof(dp)); memset(pri,0,sizeof(pri)); for(int i=0;imax) max=pri[i],mark=i; } pri[mark]=0; scanf("%d",&m); m=m-5; int count=0; for(int i=0;i=pri[i];j--) { if(dp[j]count) count=dp[j]; } } if(m>=0) printf("%d\n",m+5-count-max); else//如果钱不够5元 printf("%d\n",m+5); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。