题解 | #购物单#

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int N, m;
    cin >> N >> m;
    N /= 10;
    vector<vector<int>> prc(m + 1, vector<int>(3, 0)); //记录价格
    vector<vector<int>> val(m + 1, vector<int>(3, 0)); //记录重要度*价格
    vector<vector<int>> dp(m + 1, vector<int>(N + 1, 0));
    for(int i = 1; i <= m; i++)
    {
        int v, p, q;
        cin >> v >> p >> q; //价格，重要度，附属
        if(q == 0)
            prc[i][0] = v/10,val[i][0] = p*v;
        else
            if(prc[q][1] == 0)
                prc[q][1] = v/10,val[q][1] = p*v;
            else
                prc[q][2] = v/10,val[q][2] = p*v;
    }
    for(int i = 1; i <= m; i++)//物品
    {
        for(int j = 1; j <= N; j++)//钱数
        {
            dp[i][j] = dp[i-1][j];//继承
            if(j >= prc[i][0])//条件1
                dp[i][j]=max(dp[i][j], dp[i-1][j-prc[i][0]]+val[i][0]);//改变1
            if(j >= prc[i][0] + prc[i][1])//条件2
                dp[i][j]=max(dp[i][j], dp[i-1][j-prc[i][0]-prc[i][1]]+val[i][0]+val[i][1]);//改变2
            if(j >= prc[i][0] + prc[i][2])//条件3
                dp[i][j]=max(dp[i][j], dp[i-1][j-prc[i][0]-prc[i][2]]+val[i][0]+val[i][2]);//改变3
            if(j >= prc[i][0]+prc[i][1] + prc[i][2])//条件4
                dp[i][j]=max(dp[i][j], dp[i-1][j-prc[i][0]-prc[i][1]-prc[i][2]]+val[i][0]+val[i][1]+val[i][2]);//改变4
        }
    }
    cout << dp[m][N] << endl;
}