车费分配c++
时间:2022-12-29 09:00:00
#include
using namespace std;
int n, k, a[101], f[101][101];
struct node {
int lf, lc;
int rf, rc;
} tn[101];
void dfs(int st) {
if (tn[st].lc != 0)
dfs(tn[st].lc);
if (tn[st].rc != 0)
dfs(tn[st].rc);
if (tn[st].lc != 0) {
for (int i = k; i >= tn[st].lf; i--)
for (int j = 0; j <= i - tn[st].lf; j )
f[st][i] = max(f[st][i], f[st][i - tn[st].lf - j] f[tn[st].lc][j]);
}
if (tn[st].rc != 0) {
for (int i = k; i >= tn[st].rf; i--)
for (int j = 0; j <= i - tn[st].rf; j )
f[st][i] = max(f[st][i], f[st][i - tn[st].rf - j] f[tn[st].rc][j]);
}
for (int i = 0; i <= k; i ) f[st][i] = a[st];
}
int main() {
// freopen("distribution.in", "r", stdin);
// freopen("distribution.out", "w", stdout);
cin >> n >> k;
for (int i = 1; i <= n; i ) {
cin >> a[i];
}
for (int i = 1; i <= n; i ) {
int lc1, lf1, rc1, rf1;
cin >> lc1 >> lf1 >> rc1 >> rf1;
tn[i].lc = lc1;
tn[i].lf = lf1 * 2;
tn[i].rc = rc1;
tn[i].rf = rf1 * 2;
}
dfs(1);
cout << f[1][k];
return 0;
}