艺术馆最多有100个展室 ------> 节点数$<=100*2<2^{8}=256$
所以可以开一个$f[i][j]$表示到第$i$个点为止花去$j$分钟的最大价值
对于分叉的点，我们可以直走右边或直走左边，也可以两边都走一次，分别转移即可。
对于展室（叶节点），处理一下几分钟能拿几幅画。
因为要折返所以边权$*2$，并且总时间花费要严格小于deadline，所以总时间-1
#include<iostream> #include<cstdio> #include<cstring> #define re register using namespace std; int min(int a,int b){return a<b?a:b;} int max(int a,int b){return a>b?a:b;} int rt,u,s,f[302][602]; int dfs(int &o){ int d,v,lc,rc; o=++u; scanf("%d%d",&d,&v); if(!v){ int ld=dfs(lc),rd=dfs(rc); for(int i=s;i>=ld;--i) f[o][i]=max(f[o][i],f[lc][i-ld]);//只走左边 for(int i=s;i>=rd;--i) f[o][i]=max(f[o][i],f[rc][i-rd]);//只走右边 for(int i=ld;i<=s;++i) for(int j=rd;i+j<=s;++j) f[o][i+j]=max(f[o][i+j],f[lc][i-ld]+f[rc][j-rd]);//两边都走 }else{ for(int i=0;i<=s;++i) f[o][i]=min(i/5,v);//叶节点处理 }return d<<1;//边权*2 } int main(){ scanf("%d",&s); --s; s-=dfs(rt); printf("%d",f[rt][s]); return 0; }
原文：https://www.cnblogs.com/kafuuchino/p/9866706.html
