洛谷P1757 通天之分组背包

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

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

int main()
{
    int m, n;
    cin >> m >> n;
    int cost[101][1001] = { 0 };
    int value[101][1001] = { 0 };
    int ans[101] = { 0 };
    int x = 0;
    for (int i = 0; i < n; i++){
        int a, b, c;
        cin >> a >> b >> c;
        if (c>x){
            x = c;
        }
        cost[c][ans[c]] = a;
        value[c][ans[c]++] = b;
    }
    int pos[1001] = { 0 };
    for (int i = 0; i <= x; i++){
        for (int j = m; j >= 0; j--){
            for (int k = 0; k < ans[i]; k++){
                if (j >= cost[i][k]){
                    pos[j] = max(pos[j], pos[j - cost[i][k]] + value[i][k]);
                }
            }
        }
    }
    cout << pos[m] << endl;




    return 0;
}