【codevs1163】访问艺术馆

时间:2021-11-14 22:25:30
题目描述

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

【codevs1163】访问艺术馆

输入

第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]]]);
}
}
}
int main()
{
scanf("%d" , &s);
input();
dp(1);
printf("%d\n" , f[1][s - 2 * t[1]]);
return 0;
}