洛谷P1064 金明的预算方案

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;

struct MAP {
    int cost;
    int value;
};

int max(int a, int b){
    return a > b ? a : b;
}

int main()
{
    deque<MAP> v[61];
    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= n; i++){
        int a, b, c;
        cin >> a >> b >> c;
        MAP t;
        t.cost = a;
        t.value = a*b;
        if (c == 0){
            v[i].push_front(t);
        }
        else{
            v[c].push_back(t);
        }
    }


    int pos[32000] = { 0 };

    for (int i = 1; i <= n; i++){
        if (!v[i].empty() && m >= v[i][0].cost){
            int temp[32000] = { 0 };
            int e = m - v[i][0].cost;
            for (int j = 1; j <= m; j++){
                temp[j] = pos[j];
            }
            for (int j = 1; j < v[i].size(); j++){
                for (int k = e; k >= v[i][j].cost; k--){
                    temp[k] = max(temp[k], temp[k - v[i][j].cost] + v[i][j].value);
                }
            }
            for (int j = m; j >= v[i][0].cost; j--){
                pos[j] = max(pos[j], temp[j - v[i][0].cost] + v[i][0].value);
            }
        }
    }

    cout << pos[m] << endl;





    return 0;
}