|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include <iostream> #include <sstream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; int price[1005]; int dp[2][1100]; int main(){ int n; while (cin >> n && n) { memset(price, 0, sizeof(price)); for (int i = 1; i <= n; i++) { cin >> price[i]; } int m; cin >> m; if (m < 5) { cout << m << endl; continue;//hehe } sort(price+1, price+1+n); memset(dp, 0xf3f3, sizeof(dp)); dp[0][0] = 0; int res = 0; for (int i = 1; i < n; i++) { for (int j = 0; j <= m-5; j++) { if(j-price[i]>=0) dp[i%2][j] = max(dp[(i-1)%2][j-price[i]]+price[i],dp[(i-1)%2][j]); else dp[i%2][j] = dp[(i-1)%2][j]; res = max(res,dp[i%2][j]); } } cout << m-(res+price[n]) << endl; } return 0; } |
这道题给我玩惨了，原因就是“hehe”那里没有加，后果是啥大家都知道。。。
其实是一个包装过了的01背包问题，既然>=5块时都能随便花，那么我就把最贵的那个留下，然后尽量把饭卡刷到还剩5块钱的程度（不一定是五块，但尽量靠近五块），然后再去买那个最贵的，一次性刷爆。（虽然还是有可能刷不爆的，但余额尽量小是真的），“尽量把饭卡刷到还剩5块钱的程度”，这个就可以转化为重量限定m－5，每个物品重量与价值相等情况下的01背包问题。
就这样。
