20分

离散化了

#include <bits/stdc++.h>
using namespace std;
int n, m, v[1005], w[1005], f[1005][3], len = 1, dp[1000005];
void cz();
int main () {
    cin >> n >> m;
    cz();
    /*
    for ( int i = 1; i <= len; i++ ) {
    for ( int j = 0; j <= 2; j++ ) {
    cout << f[i][j] << " ";
    }
    cout << endl;
    }
    // */
    for ( int i = 1; i <= len; i++ ) {
        for ( int j = n; j >= v[f[i][0]]; j-- ) {
            int z = f[i][0], c1 = f[i][1], c2 = f[i][2];
            dp[j] = max ( dp[j], dp[j - v[z]] + w[z] );
            if ( j >= v[z] + v[c1] ) dp[j] = max ( dp[j], dp[j - v[z] - v[c1]] + w[z] + w[c1] );
            if ( j >= v[z] + v[c2] ) dp[j] = max ( dp[j], dp[j - v[z] - v[c2]] + w[z] + w[c2] );
            if ( j >= v[z] + v[c2] + v[c1] ) dp[j] = max ( dp[j], dp[j - v[z] - v[c2] - v[c1]] + w[c2] + w[z] + w[c2] );
        }
    }
    cout << dp[n];
    return 0;
}
void cz() {
    for ( int i = 1; i <= m; i++ ) {
        int p, q;
        cin >> w[i] >> p >> q;
        v[i] = w[i];
        w[i] *= p;
        if ( q == 0 ) f[i][0] = 1;
        else {
            if ( f[q][1] != 0 ) f[q][2] = i;
            else f[q][1] = i;
        }
    }
    if ( f[1][0] == 1 ) len = 2;
    for ( int i = 2; i <= m; i++ ) {
        if ( f[i][0] == 1 ) {
            if ( len != i ) {
                f[len][1] = f[i][1], f[len][2] = f[i][2];
                f[i][0] = f[i][1] = f[i][2] = 0;
            }
            f[len][0]=i,len++;
        }
    }
    len--;
}