wikioi 1163 訪问艺术馆 树形dp
2024-08-26 22:03:41
递归建树,由题知该树是一棵二叉树,且除根节点外其它点的度为0或2。
dp[i][j]表示来到第i个走廊(还未走过这条走廊)还剩下j时间,能拿到最大的画的数量。
dp[i][j]=max(dp[i][j],dp[lson[i]][k]+dp[rson][last_time-k])
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[200][700];
int id=0,x,y,s;
struct node
{
int t,l,r;
int v;
}tree[200];
void init(int now)
{
scanf("%d%d",&x,&y);
tree[now].t=x*2;
tree[now].v=y;
if(y!=0) tree[id].l=tree[id].r=-1;
else
{
tree[now].l=++id;init(id);
tree[now].r=++id;init(id);
}
}
int dfs(int now,int times)
{
if(dp[now][times]) return dp[now][times]; //记忆化
int last=times-tree[now].t;
if(last<0) return 0;
if(tree[now].l==-1) return dp[now][times]=min(tree[now].v,last/5);
int maxn=0;
for(int i=0;i<=last;i++)
{
maxn=max(maxn,dfs(tree[now].l,i)+dfs(tree[now].r,last-i)); /*这里会调用多次已经计算过的值*/
//计算左儿子i时间,右儿子last-i时间的最大偷画数
}
return dp[now][times]=maxn;
}
int main()
{
scanf("%d",&s);
init(0);
printf("%d\n",dfs(0,s));
return 0;
}
最新文章
- Thinkphp3.2----------------Thinkphp3.2的目录结构介绍
- 从体系架构上分析PRINCE2和pmp的区别
- js断点调试心得
- 你会swap吗,按值传递还是按引用?
- Java for LeetCode 060 Permutation Sequence
- WCF帮助类
- Linux权限体系总结
- Java Socket Example
- python运行时间计算之timeit
- copy指定目录下包括子目录中所有的文件
- EasyNetQ WithTopic过滤失效的解决方案
- 深圳奥特迅现金流量——RESSET数据库
- mysql中使用存储过程方法中的注意事项
- Unity插件扩展中组件常用的几个方法
- [JAVA]为什么==和equals总让新手迷惑? 详解 关系操作符 == 和 equals
- Windows下 Robhess SIFT源码配置
- 关于ajax请求,返回json数据格式
- 冒烟测试(smoke testing)
- Problem E: 编写函数:Swap (I) (Append Code)
- sql 游标 跳出循环 和进入下一个循环