“访问“美术馆

前言

今天学习了树形DP,用这道练练手

---

传送门 初拿到题有些棘手,因为不知道如何表示状态,再仔细一推,发现与树形背包相似,所以我们设dp[now][k] 表示以now为根结点时用了time分钟能获得的最大画数 如果now是展室,设s为now的画数,k为选取的画数,那么dp[now][5k]=${\sum }_{k=1}^{s}dp[now][5\ast k-5]$ 其中,time+5k<=m 即:

for(int i=1;i<=a[now].val;i++) { int s=tt+i*5; if(s>m) { break; } dp[now][s]=dp[now][s-5]+1; }

而如果now是有两条分叉的走廊,我们可以把它抽象成一个没有画的房间,先遍历它的左子树和右子树,递归得到答案后,设左子树花费i秒偷盗,右子树花费j秒偷盗,则:

for(int i=0;i<=m-tt;i++){ for(int j=0;j<=m-tt-i;j++) { dp[now][tt+i+j]=max(dp[now][tt+i+j],dp[l][tt+i]+dp[r][tt+j]); } }

输入时,还是用递归,如果是分叉走廊,则设这三条走廊分别为x(当前编号),2x,2x+1保证遍历时的有序 完整代码:

#include<cstdio> #include<iostream> using namespace std; int n,dp[605][605],m; struct ren{ int t,val; }a[1005]; void init(int x) { scanf("%d%d",&a[x].t,&a[x].val); a[x].t*=2;//最后要返回入口,每个走过的边要往返走一次 if(!a[x].val)//是分叉走廊 { init(x*2); init(x*2+1); } } void dfs(int now,int tt) { if(a[now].val) { for(int i=1;i<=a[now].val;i++) { int s=tt+i*5; if(s>m) { break; } dp[now][s]=dp[now][s-5]+1; } } else{ int l=now*2,r=now*2+1; dfs(l,tt+a[l].t);//遍历左子树 dfs(r,tt+a[r].t);//遍历右子树 for(int i=0;i<=m-tt;i++){ for(int j=0;j<=m-tt-i;j++) { dp[now][tt+i+j]=max(dp[now][tt+i+j],dp[l][tt+i]+dp[r][tt+j]);//时间为左子树所用时间+右子树所用时间 } } } } int main() { scanf("%d",&m); m-=1;//当你刚好走到入口时警察来了也跑不了 init(1); dfs(1,a[1].t);//从第一个走廊进入,至少都要花第一个走廊的时间 printf("%d\n",dp[1][m]); return 0; }

附赠:偷天换日