https://vijos.org/p/1313

//}/* .................................................................................................................................. */

const int N = int(61), M = int(3.2e4) + 9;
int f[M]; int n, m;
VI adj[N]; int c[N], v[N], p[N];

VII Pack; void get(int u){
    CLR(Pack); Pack.PB(MP(c[u], v[u]));
    ECH(it, adj[u]) Pack.PB(MP(c[u]+c[*it], v[u]+v[*it]));
    if (SZ(adj[u]) == 2) Pack.PB(MP(c[u]+c[adj[u][0]]+c[adj[u][1]], v[u]+v[adj[u][0]]+v[adj[u][1]]));
}



int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(m, n);
    REP_1(i, n){
        RD(c[i], v[i], p[i]); v[i] *= c[i];
        if (p[i]) adj[p[i]].PB(i);
    }


    REP_1(i, n){
        if (p[i]) continue;
        get(i); DWN_1(j, m, 0){
            ECH(it, Pack) if (j >= it->fi){
                checkMax(f[j], f[j-it->fi] + it->se);
            }
        }
    }
    cout << f[m] << endl;
}

Posted by xiaodao
Category: 日常