HDU 2546 饭卡

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 int main(){
 8     int n;
 9     while(cin >>n && n){
10         vector<int> food(n);
11         for(int i = 0; i < n; i ++ ) cin >> food[i];
12         int price;
13         cin >> price;
14         if(price < 5) {cout<<price<<endl;continue;}
15         sort(food.begin(),food.end());
16         vector<int> dp(price - 5 + 1, 0);
17         for(int i =0; i < n-1; i ++ ){
18             for(int j = price - 5 ; j >= food[i]; j --){
19                 dp[j] = max(dp[j],dp[j - food[i]]+food[i]);
20             }
21         }
22         cout<< price - dp[price-5] - food[n-1]<<endl;
23 
24     }
25     return 0;
26 }