P1270 “访问”美术馆

· · 题解

这道题感觉是树形DP“青春版”

就只用深搜和回溯（回溯的时候干干DP之事）就可以过

遍历到叶子的时候将其特殊处理一下

要注意几点：首先是每条路都要走两次（小偷总不能在管里头过夜），其次是最后一秒（不可以和阿sir撞个满怀）

最后给出代码（详细注解）

#include<iostream>
#include<cstdio>
using namespace std;
int f[100100][610];
int ls[100100],rs[100100];
int t,tot;
void build(int now)//dfs
{
    int x,y;//x代表路径长度
    scanf("%d%d",&x,&y);
    if(y==0)
    {
        ls[now]=++tot;build(ls[now]);
        rs[now]=++tot;build(rs[now]);
        for(int i=x*2+1;i<=t;i++)//从走完这条走廊的时间到最后
        for(int j=0;j<=i-x*2;j++)
//左儿子分配j的时间，右二子分配（i-2*x-j），也就是走完之前的走廊分配给儿子的时间减去左儿子分配到的时间
        f[now][i]=max(f[now][i],f[ls[now]][j]+f[rs[now]][i-2*x-j]);
    }
    else
    {
        for(int i=x*2+5;i<=min(x*2+y*5,t);i++)f[now][i]=(i-x*2)/5;
//这是叶子节点，所以只管偷画（应该可以不用这个min）
        for(int i=x*2+y*5+1;i<=t;i++)f[now][i]=f[now][i-1];
//画不够偷注意补齐喔
    }
}
int main()
{
    scanf("%d",&t);
    build(0);
    printf("%d",f[0][t-1]);
    return 0;
}