洛谷 P1270 “访问”美术馆 解题报告

P1270 “访问”美术馆

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

输出偷到的画的数量

---

读懂题了其实也不难。

首先很有意思的是dfs输入数据

然后直接做树上分组背包就行啦。注意在最后一秒是跑不掉的

---

Code：

#include <cstdio>

int max(int x,int y){return x>y?x:y;}

const int N=602;

int dp[N][N],t,ch[N][2],dat[N],num[N],root,cnt;

int dfs()

{

    int now=++cnt;

    scanf("%d%d",&dat[now],&num[now]);

    dat[now]*=2;

    if(!num[now])

    {

        ch[now][0]=dfs();

        ch[now][1]=dfs();

    }

    return now;

}

void init()

{

    scanf("%d",&t);

    root=dfs();

}

void dfs_dp(int now)

{

    if(!num[now])

    {

        for(int i=0;i<=1;i++)

        {

            dfs_dp(ch[now][i]);

            for(int j=t;j;j--)

                for(int k=0;k<=j;k++)

                    dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[ch[now][i]][k]);

        }

        for(int i=t;i>=dat[now];i--)

            dp[now][i]=dp[now][i-dat[now]];

        for(int i=0;i<=dat[now];i++)

            dp[now][i]=0;

    }

    else

    {

        for(int i=1;i<=num[now]&&i*5+dat[now]<=t;i++)

            dp[now][i*5+dat[now]]=i;

    }

}

int main()

{

    init();

    dfs_dp(root);

    int ans=0;

    for(int i=1;i<=t;i++)

        ans=max(ans,dp[root][i]);

    printf("%d\n",ans);

    return 0;

}

---

2018.7.7