budget.cpp

#include <cstdlib>
#include <cstring>
#include <cstdio>
#define MAX_ITEM 62
#define MAX_MONEY 32002

int n; 
int money; 
int cost[MAX_ITEM]; 
int value[MAX_ITEM]; 
bool relationship[MAX_ITEM][MAX_ITEM]; 
bool have_attach[MAX_ITEM]; 
bool is_attach[MAX_ITEM]; 
int f[MAX_MONEY]; 

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

int main() {
    FILE *fin = fopen("budget.in", "r"); 
    FILE *fout = fopen("budget.out", "w"); 
    int a, b; 
    fscanf(fin, "%d %d", &money, &n); 
    for(int i = 0; i < n; i++) {
        fscanf(fin, "%d %d %d", &cost[i], &value[i], &a); 
        if(a) {
            a = a - 1; 
            relationship[a][i] = true; 
            is_attach[i] = true; 
            have_attach[a] = true; 
        }
    }
    for(int i = 0; i < n; i++) {
        if(is_attach[i]) {
            continue; 
        }
        for(int j = money; j >= cost[i]; j--) {
            f[j] = fmax(f[j], f[j - cost[i]] + value[i] * cost[i]); 
            if(have_attach[i]) {
                // if have attach
                // a means total cost here
                // b means total value here
                a = 0;
                b = 0; 
                for(int k = 0; k < n; k++) {
                    if(relationship[i][k]) {
                        if(j - cost[i] - cost[k] >= 0) {
                            f[j] = fmax(f[j], f[j - cost[i] - cost[k]] + value[i] * cost[i] + value[k] * cost[k]);
                        }
                        a = a + cost[k]; 
                        b = b + value[k] * cost[k]; 
                    }
                }
                if(j - a - cost[i]>= 0) {
                    f[j] = fmax(f[j], f[j - a - cost[i]] + value[i] * cost[i] + b); 
                }
            }
        }
    }
    fprintf(fout, "%d\n", f[money]); 
    return 0; 
}