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

代碼：

?#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
int dp[1005];
int main()
{
? ? int n,m,a[1005],i,j,k;
? ? while(~scanf("%d",&n))
? ? {
? ? ? ? if(n==0)
? ? ? ? ? ? break;
? ? ? ? memset(dp,0,sizeof(dp));
? ? ? ? memset(a,0,sizeof(a));
? ? ? ? for(i=0;i<n;i++)
? ? ? ? ? ? cin>>a[i];
? ? ? ? cin>>m;
? ? ? ? if(m<5)//如果金額小于5，什么也不能買
? ? ? ? {
? ? ? ? ? ? printf("%d\n",m);
? ? ? ? ? ? continue;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? sort(a,a+n);//排序
? ? ? ? ? ? dp[0]=0;
? ? ? ? ? ? for(i=0;i<n-1;i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? for(j=m-5;j>=a[i];j--)
? ? ? ? ? ? ? ? ? ? dp[j]=max(dp[j],dp[j-a[i]]+a[i]);//除去最大的菜后最多能買菜所花的金額
? ? ? ? ? ? }
? ? ? ? ? ? printf("%d\n",m-(dp[m-5]+a[n-1]));卡里金額減掉除去最大的菜后最多能買菜所花的金額和最大的菜所花的金額
? ? ? ? }
? ? }
? ? return 0;
}

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。