P1802 5 倍经验日 01背包

01背包问题 参考：1. P1060 [NOIP2006 普及组] 开心的金明 java_ 01背包 2. P1048 采药 java 01背包 3. 当题目的价值比较大的时候，我们要注意数据范围的问题，此题需要用龙long long类型，不然最后一个点过不去； 4. 在能满足嗑药的时候，我们通过选择嗑药或者不嗑药，去选择其中能达到最大价值的选择； 5. dp[i][j]表示：对于前i个人，在药瓶还可以选择j的时候，所能达到商品的最大价值； 6. 最后不要忘记乘5；

#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
ll dp[1010][1010];
int lose[1010];
int win[1010];
int use[1010];

int main() {
    int n, x;
    cin >> n >> x;
    for (int i = 1; i <= n; ++i) {
        cin >> lose[i];
        cin >> win[i];
        cin >> use[i];
    }
    for (int i = 1; i <= n; i++) {//n个人
        for (int j = 0; j <= x; ++j) {//共x瓶药
            if (j >= use[i]) {//可以嗑药 那么两种选择
                dp[i][j] = max(dp[i - 1][j] + lose[i], dp[i - 1][j - use[i]] + win[i]);//不嗑药或者嗑药
            } else {//只能失败
                dp[i][j] = dp[i - 1][j] + lose[i];
            }
        }
    }
    cout << dp[n][x] * 5;
    return 0;
}