題目連結:傳送門 題面:
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
Sample Output
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <vector>
#include <iomanip>
#define
#define
#define
using namespace std;
int n, w[A], V, ans, f[A];
int main() {
while (cin >> n) {
if (!n) return 0;
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i++) cin >> w[i];
sort (w + 1, w + n + 1);
cin >> V;
if (V < 5) {
cout << V << endl;
continue;
}
V -= 5;
for (int i = 1; i < n; i++)
for (int j = V; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + w[i]);
cout << V + 5 - f[V] - w[n] << endl;
}
}