饭卡

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

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:  2602 2955 1203 2159 2191 

 

1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<stack> 5 #include<set> 6 #include<map> 7 #include<queue> 8 #include<algorithm> 9 using namespace std; 10 int price[1005],dp[1005]; 11 #define max(a,b) (a>b?a:b) 12 int main() 13 { 14 //freopen("D:\\INPUT.txt","r",stdin); 15 int n,m,i,j; 16 while(scanf("%d",&n)!=EOF) 17 { 18 if(!n){ 19 break; 20 } 21 memset(dp,0,sizeof(dp)); 22 for(i=0; i<n; i++) 23 { 24 scanf("%d",&price[i]); 25 } 26 sort(price,price+n); 27 scanf("%d",&m); 28 if(m<5){ 29 printf("%d\n",m); 30 continue; 31 } 32 m-=5; 33 n--; 34 for(i=0; i<n; i++) //放入第i种菜 35 { 36 for(j=m; j>=price[i]; j--) 37 { 38 //对于dp[j]=max(dp[j],dp[j-price[i]+price[i]]) 39 dp[j]=max(dp[j],dp[j-price[i]]+price[i]); 40 } 41 } 42 printf("%d\n",m+5-dp[m]-price[n]); 43 } 44 return 0; 45 }

 

转载于:https://www.cnblogs.com/Deribs4/p/4796046.html

总结

以上是生活随笔为你收集整理的hduoj 2546饭卡的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。