洛谷 P1270 “访问”美术馆 题解【树形DP】【模拟】【递归】

点击量：230

   输入格式不好玩。。。

目录

题目描述

经过数月的精心准备，Peer Brelstet，一个出了名的盗画者，准备开始他的下一个行动。艺术馆的结构，每条走廊要么分叉为两条走廊，要么通向一个展览室。Peer知道每个展室里藏画的数量，并且他精确测量了通过每条走廊的时间。由于经验老到，他拿下一幅画需要5秒的时间。你的任务是编一个程序，计算在警察赶来之前，他最多能偷到多少幅画。

输入输出格式

输入格式：

第1行是警察赶到的时间，以s为单位。第2行描述了艺术馆的结构，是一串非负整数，成对地出现：每一对的第一个数是走过一条走廊的时间，第2个数是它末端的藏画数量；如果第2个数是0，那么说明这条走廊分叉为两条另外的走廊。数据按照深度优先的次序给出，请看样例。

 

一个展室最多有20幅画。通过每个走廊的时间不超过20s。艺术馆最多有100个展室。警察赶到的时间在10min以内。

 

输出格式：

输出偷到的画的数量

 

输入输出样例

输入样例#1：

60

7 0 8 0 3 1 14 2 10 0 12 4 6 2

 

输出样例#1：

2

题解：

   首先要注意的地方是警察赶来之前，这样当时间刚好为输入的第一行t0时，是不满足题意的，最好的做法是读入t0后将t0–。

   还有一处理解问题就是在t0的时间段内，小偷需要做的是从入口进去、偷东西，再从这些走廊出来，每条路一定会被经过两次，那我们dfs过程中读入走廊长度，×2存在时间里。同时看到每个交叉点只会扩展为2条走廊，所以这是一棵二叉树(与多叉树也没有什么区别)。

   这样建树，就完全转化为树形DP了，对于状态，我们用f[i][j]表示以i为根节点的子树中，花费j的时间最多能偷到多少幅画。再用类似背包的转移就行了，要枚举时间总和以及部分时间。总时间复杂度为$ O(nt_0^2)$N表示节点个数（不是画室）,t0表示警察还有多少秒到达战场2333因为最多有100个画室，所以预估有400个节点。

Code：

#include<cstdio>
#include<cstring>
int max(int x,int y)
{
    return x>y?x:y;
}
struct edge
{
    int n,v,nxt;
    edge(int n,int v,int nxt)
    {
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[1000];
int head[500],ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,v,head[from]);
    head[from]=ecnt;
}
int t0;
int h[500],cnt;
void build(int x,int from)//递归输入建树
{
    cnt=x;
    int t,n;
    scanf("%d%d",&t,&n);
    add(from,x,2*t);
    h[x]=n;
    if(n)
        return;
    build(cnt+1,x);
    build(cnt+1,x);
}
int f[666][2100],tm=0;
void dfs(int x)
{
    for(int i=head[x];~i;i=e[i].nxt)
    {
        dfs(e[i].n);
        for(int j=t0;j>=0;j--)//DP过程
            for(int k=0;k<=j;k++)
                if(j-e[i].v-k>=0)
                    f[x][j]=max(f[x][j],f[x][j-e[i].v-k]+f[e[i].n][k]);
    }
    if(h[x])//DP边界
        for(int j=t0;j>=0;j--)
            for(int i=1;i<=h[x];i++)
                if(j>=5*i)
                    f[x][j]=i;
    return;
}
int main()
{
    memset(head,-1,sizeof(head));
    int sum=0;
    scanf("%d",&t0);
    t0--;
    build(1,0);
    dfs(0);
    printf("%d\n",f[0][t0]);
    return 0;
}