|
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 53 54 55 56 57 58 59 60 61 62 |
#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; struct itemType{ int p,q,v; }; int dp[505][5005];//before puchase itemType item[505]; bool cmp(itemType a,itemType b){ return a.q-a.p > b.q-b.p; } int main(){ int n = 0,m = 0; while(cin >> n >> m){ memset(dp, 0, sizeof(dp)); memset(item, 0, sizeof(item)); int res = 0; for (int i = 1; i <= n;i++) { cin >> item[i].p >> item[i].q >> item[i].v; } sort(item+1, item+1+n, cmp); for (int i = 1; i <= n; i++) { for(int j = m;j >= 0;j--) { if (j < item[i].q) { //cannot buy dp[i][j] = max(dp[i-1][j],dp[i][j]); }else{ //can buy dp[i][j] = max(dp[i-1][j],dp[i][j]); dp[i][j-item[i].p] = max(dp[i-1][j]+item[i].v,dp[i-1][j]); } res = max(res,dp[i][j]); } } cout << res << endl; } return 0; } |
这是个需要排序预处理的01背包问题（够sxbk），排序的基准是q-p小的在前。
至于为啥。。。我是可耻的翻了题解才知道怎么做的，这位讲的清楚明白：
