洛谷P1270 树形DP

题目描述

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

输入输出格式

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

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

输出偷到的画的数量

观察发现其实给你的输入就是一棵树

注意给你的时间要减一。在警察来之前

树形DP即可。

#include<cstdio>
#include<algorithm>
using namespace std;
struct q{
int ls,rs,time,value;
}tree[201];
int n,x,y,cnt,dp[201][601];
void read(int fa)
{
scanf("%d%d",&x,&y);
cnt++;int t=cnt;
if (tree[fa].ls==0) tree[fa].ls=cnt;else tree[fa].rs=cnt;
tree[cnt].time=x;
if (y==0) read(t),read(t);
else tree[cnt].time=x,tree[cnt].value=y;
}
void dfs(int x)
{
if (tree[x].value)
{
for (int i=tree[x].time*2;i<=n;i++)
dp[x][i]=min((i-tree[x].time*2)/5,tree[x].value);
}
else
{
dfs(tree[x].ls);dfs(tree[x].rs);
for (int i=tree[x].time*2;i<=n;i++)
for (int j=0;j<=i-tree[x].time*2;j++)
{
dp[x][i]=max(dp[x][i],dp[tree[x].ls][j]+dp[tree[x].rs][i-tree[x].time*2-j]);
}
}
}
int main()
{
scanf("%d",&n);n--;
read(0);
dfs(1);
printf("%d",dp[1][n]);
return 0;
}

最后

以上就是碧蓝春天为你收集整理的洛谷P1270 树形DP的全部内容，希望文章能够帮你解决洛谷P1270 树形DP所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。