题解 | #购物单#

//https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4?tpId=37&rp=1&ru=%2Fexam%2Foj%2Fta&qru=%2Fexam%2Foj%2Fta&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26pageSize%3D50%26search%3D50%26tpId%3D37%26type%3D37&difficulty=&judgeStatus=&tags=&title=%E8%B4%AD%E7%89%A9&gioEnter=menu

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

using namespace std;

int main() {
    int m = 0;
    int n = 0;

    while (cin >> m >> n) {
        m/=10;  //价钱/10看作背包容量

        vector<vector<int>> price(n+1, vector<int> (3, 0));
        vector<vector<int>> value(n+1, vector<int> (3, 0));
        vector<vector<int>> ans(n+1, vector<int> (m+1, 0));


        for(int i = 1;i<=n;i++){
            int v = 0;
            int p = 0;
            int q = 0;

            cin >> v >> p >> q;
            v/=10;

            if(q==0){
                price[i][0] = v;
                value[i][0] = p;

            }else if(price[q][1]!=0){
                    price[q][2] = v;
                    value[q][2] = p;
                }else{
                    price[q][1] = v;
                    value[q][1] = p;
                }

        }

        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=m;j++){    //复制for循环时一定注意检查变量
                int a = price[i][0], b = value[i][0];
                int c = price[i][1], d = value[i][1];
                int e = price[i][2], f = value[i][2];
                ans[i][j] = j>=a? max(ans[i-1][j], ans[i-1][j-a]+a*b):ans[i-1][j];
                ans[i][j] = j>=a+c? max(ans[i][j], ans[i-1][j-a-c]+a*b+c*d):ans[i][j];  //要不要1附件
                ans[i][j] = j>=a+e? max(ans[i][j], ans[i-1][j-a-e]+a*b+e*f):ans[i][j];  //要不要2附件
                ans[i][j] = j>=a+c+e? max(ans[i][j], ans[i-1][j-a-c-e]+a*b+c*d+e*f):ans[i][j];  //要不要1附件+2附件，没项都是在前一项的基础上进行对比，所以不要的情况为ans[i][j]

            }

        cout << ans[n][m]*10 << endl;

    }
}