题解 | #购物单#

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
    // 0-1背包标志公式  d[i][j]= max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]) 
    //  i 为物品   j为拥有的钱财 死死抓住i和j的含义 以物品i为核心  目前不知道放不放i 但是j是固定的 
    // 为什么是di[i-1][j]   
    // 为什么j不用考虑已经选的？ 因为在考虑max的时候 就已经考虑放不放得下当前物品了 每次都是满钱的状态去判断 算的是总值
    // 所以是取max 
    // 主件     
    //这里存在一个疑问 为什么输入数据时 i的作用仅在主件时生效？
    // 错误猜想：输入顺序存在要求  -> 主件后面必须跟对应的附件才行
     //因为 hasAttachments即为i的编码
int main(){
	int N, m; // N 奖金 m 物品个数
    cin >> N >> m;
    N /= 10; // 由于所有的价格都是10的整倍数，所以可以均除10以简化运算复杂度

    int price, priority, hasAttachments;
    vector<vector<int>> data(m+1, vector<int>(6, 0));

    for(int i = 1; i <= m; i++){
        cin >> price >> priority >> hasAttachments;
        if(hasAttachments == 0){
            data[i][0] = price/10;
            data[i][1] = priority;
            // count++;
        }
        else if(data[hasAttachments][2] == 0){
            data[hasAttachments][2] = price/10;
            data[hasAttachments][3] = priority;
        }
        else {
            data[hasAttachments][4] = price/10;
            data[hasAttachments][5] = priority;
        }
    }

	vector<int> dp(N+1, 0);
    for(int i = 1; i < m+1; i++){
        for(int j = N; j >= 1; j--){
            int pricePrime = data[i][0];
            int priceAtta1 = data[i][2];
            int priceAtta2 = data[i][4];
            
            int priorPrime = data[i][1];
            int priorAtta1 = data[i][3];
            int priorAtta2 = data[i][5];

            dp[j] = j >= pricePrime ? max(dp[j - pricePrime]
                                            + priorPrime * pricePrime, 
                                            dp[j]) : dp[j];
            dp[j] = j >= (pricePrime + priceAtta1) ? max(dp[j - pricePrime - priceAtta1]
                                                        + priorPrime * pricePrime 
                                                        + priorAtta1 * priceAtta1, 
                                                        dp[j]) : dp[j];
            dp[j] = j >= (pricePrime + priceAtta2) ? max(dp[j - pricePrime - priceAtta2]
                                                        + priorPrime * pricePrime 
                                                        + priorAtta2 * priceAtta2, 
                                                        dp[j]) : dp[j];
            dp[j] = j >= (pricePrime + priceAtta1 + priceAtta2) ? 
                                                        max(dp[j - pricePrime - priceAtta1 - priceAtta2]
                                                        + priorPrime * pricePrime 
                                                        + priorAtta1 * priceAtta1
                                                        + priorAtta2 * priceAtta2, 
                                                        dp[j]) : dp[j];
        }
    }
    cout << dp[N] * 10 <<endl;
    return 0;
}