题解 | #购物单#

1. 注意基本的背包问题的变化版本而已。
2. 由于价格是10的整数倍，处理一下以降低空间/时间复杂度
3. 并行判断技巧。(由于后三种情况是在放a的基础上，所以不满足的条件为 dp[i][j])
4. 数组总要开大一个以及读取三元组的技巧

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N, m;
    cin>>N>>m;
    // 由于价格是10的整数倍，处理一下以降低空间/时间复杂度
    N/= 10; //否则开出的DP将会非常的大，最后结果记得乘个10就行

    //商品编号从1开始，所以要比既定目标大一个
    vector<vector<int>> prices(60, vector<int>(3,0));// 价格
    vector<vector<int>> priceMultiplyPriority(60, vector<int>(3,0)); // 重要程度


    for(int i = 1; i<=m;i++){
        int v, p,q;
        cin>>v>>p>>q;

        v /=10; p*= v; // 每件商品除以10减少复杂度，以及顺便把最后的权重算出来（就是两项的乘积）
        if(q==0){
            prices[i][0] = v; // 录入主件的加个
            priceMultiplyPriority[i][0] = p;//录入主件的权重
        }else{
            if(prices[q][1]==0){// 所属主键的第一个附件
                prices[q][1] = v;
                priceMultiplyPriority[q][1] = p;
            }else{// 所属主键的第二个附件
                prices[q][2] = v;
                priceMultiplyPriority[q][2] = p;
            }
        }

    }

    // 使用分组背包
    vector<vector<int>> dp(m+1, vector<int>(N+1,0));// 同时包含了初始化
    for(int i = 1; i<=m;i++){
        for(int j = 1; j<=N;j++){// 平行比较，最大的就是最大的了。如果该产品没有附件的话，那就是0，并且不会影响结果。
            int a = prices[i][0], b = priceMultiplyPriority[i][0];
            int c = prices[i][1], d = priceMultiplyPriority[i][1];
            int e = prices[i][2], f = priceMultiplyPriority[i][2];

            //平行比较
            dp[i][j] = j>=a ? max(dp[i-1][j-a]+b,dp[i-1][j]) : dp[i-1][j];
            dp[i][j] = j>= (a + c) ? max(dp[i-1][j-a-c]+b+d,dp[i][j]) : dp[i][j];
            dp[i][j] = j>= (a + e) ? max(dp[i-1][j-a-e]+b+f,dp[i][j]) : dp[i][j];
            dp[i][j] = j>= (a + c + e)? max(dp[i-1][j-a-c-e]+b + d + f,dp[i][j]) : dp[i][j];

        }
    }



    cout<<dp[m][N]*10<<endl;




    return 0;
}