飯卡

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

Problem Description 電子科大本部食堂的飯卡有一種很詭異的設(shè)計，即在購買之前判斷余額。如果購買一個商品之前，卡上的剩余金額大于或等于5元，就一定可以購買成功（即使購買后卡上余額為負(fù)），否則無法購買（即使金額足夠）。所以大家都希望盡量使卡上的余額最少。
某天，食堂中有n種菜出售，每種菜可購買一次。已知每種菜的價格以及卡上的余額，問最少可使卡上的余額為多少。

?

Input 多組數(shù)據(jù)。對于每組數(shù)據(jù)：
第一行為正整數(shù)n，表示菜的數(shù)量。n<=1000。
第二行包括n個正整數(shù)，表示每種菜的價格。價格不超過50。
第三行包括一個正整數(shù)m，表示卡上的余額。m<=1000。

n=0表示數(shù)據(jù)結(jié)束。

?

Output 對于每組輸入,輸出一行,包含一個整數(shù)，表示卡上可能的最小余額。

?

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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Deribs4/p/4796046.html

總結(jié)

以上是生活随笔為你收集整理的hduoj 2546饭卡的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。