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

作者: wjyyy 分类: DP,,树形DP,模拟,解题报告 发布时间: 2018-07-08 18:57

点击量:19

 

   输入格式不好玩。。。

 

题目描述

经过数月的精心准备,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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */