题解

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

using namespace std;

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;
}

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

using namespace std;

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;
}