题目描述

某市正在举行一场大型博览会，博览会有 n 个展馆，每个展馆里有若干个展台。这 n 个展馆以 及它们之间的道路可以看成一棵二叉树，博览会的出入口设在根节点——1 号展馆，小明将从这里 出发乘坐电瓶车到各个展馆参观，并最终回到 1 号展馆出口。

由于路程差异，乘坐电瓶车往返不同展馆间的费用也有所区别。出发时，小明的乘车卡里余额 为 k。他现在想知道，若全程都乘坐电瓶车，他最多能参观多少个展台？

说明：只要小明到达了某个展馆，就会参观该展馆内的所有展台，若多次参观同一个展台不重复计算（区级竞赛题）

输入格式

输入共 n+2 行：

第 1 行为 2 个整数 n、k，用一个空格隔开，表示展馆个数和小明乘车卡初始余额。

第 2 行为 n 个数，用一个空格隔开，表示 1 号至 n 号各展馆的展台数目。

接下来 n 行，每行 4 个数，用一个空格隔开；第 i+2 行 4 个数分别表示展馆 i 左子节点展馆号、 到左子节点展馆的费用、右子节点展馆号、到右子节点展馆的费用。如果子节点展馆号为 0 则表示 没有对应的子节点展馆

输出格式

输出共 1 行，1 个整数，表示小明最多能参观的展台数量

输入/输出例子1

输入：

10 20

2 8 5 1 10 5 9 9 3 5

2 1 3 2

4 8 5 2

6 2 7 2

8 3 9 6

0 0 10 2

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

输出：

39

样例解释

根据样例数据，可以得到如下展馆二叉树示意图（每个圈内标示了展馆号及展台数）

image.png

由图可知，小明沿红色箭号路径，到 1、2、5、3、6、7 这六个展馆参观并返回，往返乘车费用 为 18，参观展台数为 39，为能够实现的最大值。

答案

#include<bits/stdc++.h>
using namespace std;    

int n,k,a[105],b[60][100],d[70][200]; 
int jw(int p,int v)
{
    if(d[p][v]!=-1) return d[p][v]; //表示之前去过这个展馆 
    int jj=a[p];    //展馆号对应的展台数 
    int maxn=0;
    for(int i=0;i<=v;i++)
    {
        int sum=0;
        if(b[p][1]!=0&&b[p][2]<=i)  sum+=jw(b[p][1],i-b[p][2]); //往左边走 
        if(b[p][3]!=0&&b[p][4]<=v-i)  sum+=jw(b[p][3],v-i-b[p][4]); //往右边走 
        maxn=max(maxn,sum); 
    }
    d[p][v]=jj+maxn;
    return d[p][v];
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    k/=2;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=4;j++)
            cin>>b[i][j];
    fill(d[0],d[0]+70*200,-1);  //全部初始化为-1 
    cout<<jw(1,k);  //1号展馆，费用总共k元 
    return 0;
}