P1270 “访问”美术馆

典型的树形DP。

这题的建树方式非常新颖

因为是深度优先搜索输入

所以一个编号为$x$的节点

如果它里面有画那就说明它是叶子结点

如果它没有话那么就继续输入它的左儿子$x*2$和右儿子$x*2+1$

反正题目给的输入是按深搜的顺序

那么我们也不妨用深搜的方式输入！

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll t,n,m,dp[1005][605];
struct node{
    ll tm,pc;
}e[5005];
inline ll read(){
    ll x=0,f=0;
    char c=getchar();
    while(!isdigit(c))
        f|=c=='-',c=getchar();
    while(isdigit(c))
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}
inline void read(ll a){
    e[a].tm=read()*2;
    e[a].pc=read();
    if(!e[a].pc){
        read(a<<1);
        read(a<<1|1);
    }
}
inline void dfs(ll x,ll y){
    if(dp[x][y]||!y)    return;
    if(e[x].pc){
        dp[x][y]=min(e[x].pc,(y-e[x].tm)/5);
        return;
    }
    for(register int i=0;i<=y-e[x].tm;++i){
        dfs(x<<1,i);
        dfs(x<<1|1,y-e[x].tm-i);
        dp[x][y]=max(dp[x][y],dp[x<<1][i]+dp[x<<1|1][y-e[x].tm-i]);
    }
}

signed main(){
    memset(dp,0,sizeof(dp));
    t=read()-1;
    read(1);
    dfs(1,t);
    printf("%lld\n",dp[1][t]);
    return 0;
}