题解 | #购物单#

//n:0~i个物品；M:钱数 m[i-1]:第i个物品的价格v[i-1]:第i个物品的价值
//dp[n][M]

//dp[i][j]你现在有j元，现有i个物品，每个物品价格m[i]，价值v[i]，你花钱买他们，可以获得的最大价值是多少？
//初始化一个data
//背包分组

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, m;
    cin >> N >> m;
    N /= 10;
    int price, priority, hasAttachment;
    //初始化一个data (m+1)X6 将附件的price和priority放入其从属的主件行，先初始化为0，0作废
    vector<vector<int>> data(m + 1, vector<int>(6, 0));
    for (int i = 1; i <= m; ++i) { //写成m+1了
        cin >> price >> priority >> hasAttachment;
        //输入的为主件信息
        if (hasAttachment == 0) {
            data[i][0] = price / 10;
            data[i][1] = priority;
        }
        //输入的是附件
        else if (data[hasAttachment][2] == 0) { //未被占用
            data[hasAttachment][2] = price / 10;
            data[hasAttachment][3] = priority;
        } else {
            data[hasAttachment][4] = price / 10;
            data[hasAttachment][5] = priority;
        }
    }
    //分组背包
    vector<vector<int>> dp(m + 1, vector<int>(N + 1, 0)); //dp[][0]=0
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= N; ++j) {
            int pricePrime = data[i][0];
            int priceAttach1 = data[i][2];
            int priceAttach2 = data[i][4];
            int priorPrime = data[i][1];
            int priorAttach1 = data[i][3];
            int priorAttach2 = data[i][5];
            //看剩下的钱够不够买
            //只买主件0-1背包问题
            dp[i][j] = (j - pricePrime) >= 0 ? max(dp[i - 1][j],
                                                   dp[i - 1][j - pricePrime] + priorPrime * pricePrime) : dp[i - 1][j];
            //以下3种情况是附件问题，通过与只买主件得到的dp[i][j]（最大价值）作比较，结果存入dp[i][j]                                       
            //买的主件+附件1
            dp[i][j] = (j - pricePrime - priceAttach1) >= 0 ? max(dp[i][j],
                       dp[i - 1][j - pricePrime - priceAttach1] + priorPrime * pricePrime +
                       priorAttach1 * priceAttach1) : dp[i][j];
            //买的主件+附件2
            dp[i][j] = (j - pricePrime - priceAttach2) >= 0 ? max(dp[i][j],
                       dp[i - 1][j - pricePrime - priceAttach2] + priorPrime * pricePrime +
                       priorAttach2 * priceAttach2) : dp[i][j];
            //买的主件带2个附件
            dp[i][j] = (j - pricePrime - priceAttach1 - priceAttach2) >= 0 ? max(dp[i][j],
                       dp[i - 1][j - pricePrime - priceAttach1 - priceAttach2] + priorPrime *
                       pricePrime + priorAttach1 * priceAttach1 + priorAttach2 * priceAttach2) :
                       dp[i][j];
        }
    }
    cout << dp[m][N] * 10 << endl;
}

// 64 位输出请用 printf("%lld")