首页 > 代码库 > CODEVS1163访问艺术馆（第一道大师水题）
CODEVS1163访问艺术馆（第一道大师水题）
题目描述 Description
皮尔是一个出了名的盗画者，他经过数月的精心准备，打算到艺术馆盗画。艺术馆的结构，每条走廊要么分叉为二条走廊，要么通向一个展览室。皮尔知道每个展室里藏画的数量，并且他精确地测量了通过每条走廊的时间，由于经验老道，他拿下一副画需要5秒的时间。你的任务是设计一个程序，计算在警察赶来之前(警察到达时皮尔回到了入口也算)，他最多能偷到多少幅画。
输入描述 Input Description
第1行是警察赶到得时间，以s为单位。第2行描述了艺术馆得结构，是一串非负整数，成对地出现：每一对得第一个数是走过一条走廊得时间，第2个数是它末端得藏画数量；如果第2个数是0，那么说明这条走廊分叉为两条另外得走廊。数据按照深度优先得次序给出，请看样例输出描述 Output Description
输出偷到得画得数量样例输入 Sample Input
60
样例输出 Sample Output
2思路：首先读懂题意，不一定要取完一个画室中的画，取一幅画要5s，没看到这两件事，让我蛋疼的写了个简单的深搜，结果。。。错了。。。
先用递归建树，保存一下父节点，儿子节点，到父亲的距离，自己末端的画数（有的变量可能用不到）。然后开始树状dp，f[i][j]表示第i个节点取j幅画，然后对左右子树进行选择。一点点的算出来。
注意每次循环就是从0-该子树最多的画数（用一个数组保存一下），还有一点，work时，从0开始递归，因为input时把1的父节点默认为了0。。。（这个肮脏的错误让我很。。。）
code：
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
struct use{
int fa,d,va,l,r;
}a[1000];
int s,n=0,su[500]={0},ans=0;
long long f[500][10000]={0};
void input(int faa)
{
int x,y,t;
cin>>x>>y;
++n;t=n;
if (a[faa].l==0) a[faa].l=n;
else a[faa].r=n;
a[n].fa=faa;
a[n].d=x*2;
if (y==0)
{
input(t);
input(t);
}
else
a[t].va=y;
}
void work(int i)
{
int j,k,l1,l2;
if (a[i].l==0)
{
su[i]=a[i].va;
for (j=1;j<=a[i].va;++j)
f[i][j]=5*j;
return;
}
work(a[i].l);
if (i!=0)
work(a[i].r);
f[i][0]=0;
for (k=1;k<=su[a[i].r];++k)
f[i][k]=min(f[i][k],f[a[i].r][k]+a[a[i].r].d);
for (j=1;j<=su[a[i].l];++j)
f[i][j]=min(f[i][j],f[a[i].l][j]+a[a[i].l].d);
for (j=1;j<=su[a[i].l];++j)
for (k=1;k<=su[a[i].r];++k)
f[i][j+k]=min(f[i][j+k],f[a[i].l][j]+a[a[i].l].d+a[a[i].r].d+f[a[i].r][k]);
su[i]=su[a[i].l]+su[a[i].r];
}
int main()
{
int i,j;
cin>>s;
memset(a,0,sizeof(a));
memset(f,127,sizeof(f));
input(0);
work(0);
for (i=1;i<=su[0];++i)
if (f[0][i]<=s&&i>ans) ans=i;
cout<<ans<<endl;
} CODEVS1163访问艺术馆（第一道大师水题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。