首页 > 代码库 > [codevs1163]访问艺术馆

[codevs1163]访问艺术馆


题目描述

    皮尔是一个出了名的盗画者,他经过数月的精心准备,打算到艺术馆盗画。艺术馆的结构,每条走廊要么分叉为二条走廊,要么通向一个展览室。皮尔知道每个展室里藏画的数量,并且他精确地测量了通过每条走廊的时间,由于经验老道,他拿下一副画需要5秒的时间。你的任务是设计一个程序,计算在警察赶来之前(警察到达时皮尔回到了入口也算),他最多能偷到多少幅画。

技术分享
输入描述

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

输出描述

输出偷到得画得数量

样例输入

60

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

样例输出

2

数据范围及提示

s<=600

走廊的数目<=100


 

一道树形dp

由题目描述可知艺术馆是一棵二叉树,并且除了根节点以外,其余的节点要么是叶子节点,要么是有两个子树的节点。

那么我们可以将根节点和根的子树分开考虑,便于运算。

f[i][j]表示在节点i处用不多于j秒的时间最多偷的画的数量,那么当i不是叶子节点时有状态转移方程

f[i][j]=max(f[l[i]][k-t[l[i]]]+f[r[i]][j-k-t[r[i]]]),

枚举j和k即可。

注意一下最终答案不是f[1][s],因为根节点到其儿子节点的时间没有考虑。

#include <stdio.h>
int s , l[601] , r[601] , f[601][601] , v[601] , t[601] , n;
int max(int a , int b)
{
    return a > b ? a : b;
}
int min(int a , int b)
{
    return a < b ? a : b;
}
void input()
{
    n ++ ;
    int a , b , now = n;
    scanf("%d%d" , &a , &b);
    t[now] = a;
    if(b == 0)
    {
        l[now] = n + 1;
        input();
        r[now] = n + 1;
        input();
    }
    else
        v[now] = b;
}
void dp(int x)
{
    int i , j;
    if(l[x] == r[x])
    {
        for(i = s ; i >= 0 ; i -- )
            f[x][i] = min(i / 5 , v[x]);
        return;
    }
    dp(l[x]);
    dp(r[x]);
    for(i = s ; i >= 0 ; i -- )
    {
        for(j = i ; j >= 0 ; j -- )
        {
            if(j >= 2 * t[l[x]] && i - j >= 2 * t[r[x]])
                f[x][i] = max(f[x][i] , f[l[x]][j - 2 * t[l[x]]] + f[r[x]][i - j - 2 * t[r[x]]]);
            else if(j >= 2 * t[l[x]])
                f[x][i] = max(f[x][i] , f[l[x]][j - 2 * t[l[x]]]);
            else if(i - j >= 2 * t[r[x]])
                f[x][i] = max(f[x][i] , f[r[x]][i - j - 2 * t[r[x]]]);
        }
    }
    return;
}
int main()
{
    scanf("%d" , &s);
    input();
    dp(1);
    printf("%d\n" , f[1][s - 2 * t[1]]);
    return 0;
}

 

[codevs1163]访问艺术馆