博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HLG 1475 国王的宴会【树形DP】
阅读量:7030 次
发布时间:2019-06-28

本文共 1416 字,大约阅读时间需要 4 分钟。

题意:

C国在成果破解J国破坏交通的阴谋之后,国王决定宴请各位大臣,合理制定宴请的人的名单的任务就交给了作为国王智囊团团长的你。

你知道国王喜欢热闹,所以你希望能邀请尽量多的人,但是做为直接上下级关系的两个人直接出现在宴会上的时候会显得很尴尬,所以不能同时请有上下级关系的两个人。

国王是宴会的主办方,也是这个王国的最高领袖,所以必须到场。

为了能为宴会准备的更好,你需要知道整个宴会最多可以邀请多少宾客

分析: f[i][1]  表示以i为根节点并包含i的子树的最大值

       f[i][0]  表示以i为根节点不包含i的子树的最大值

       转移方程

         f[r][1]+=f[son][0];

         f[r][0]+=max(f[son][0],f[son][1]);

      PS: 可以采用 左儿子右兄弟的 的方法,将多叉树转为二叉树, 达到和领接表 类似的效果。

 

#include
#include
#define clr(x)memset(x,0,sizeof(x))#define max(a,b)(a)>(b)?(a):(b)int k,l,n;int f[1002][2];bool v[1002];struct node{ int ls,rs;}tree[6000];void dp(int r){ int son; if(!tree[r].ls&&!tree[r].rs) f[r][1]=1; // 如果是叶子节点 else { f[r][1]=1; son=tree[r].ls; // tree[i].ls 是 i 节点的直接后代 while(son) { dp(son); f[r][1]+=f[son][0]; f[r][0]+=max(f[son][0],f[son][1]); son=tree[son].rs; } }}int main(){ int i,m; while(scanf("%d%d",&n,&m)!=EOF) { clr(v); clr(tree); clr(f); while(m--) { scanf("%d%d",&k,&l); tree[l].rs=tree[k].ls; tree[k].ls=l; v[l]=1; } for(i=1;i<=n;i++) if(!v[i]) { dp(i); break; } printf("%d\n",f[i][1]); } return 0;}

 

 

 

转载于:https://www.cnblogs.com/dream-wind/archive/2012/07/19/2599914.html

你可能感兴趣的文章
数据结构---图的相关总结
查看>>
Linux平台上部署Mongoose服务器的方法介绍
查看>>
Node中间层实践(二)——搭建项目框架
查看>>
erget源码分析(2):全局哈希基类和全局异步函数对象接口
查看>>
解码方法
查看>>
Electron入门介绍
查看>>
从egg.js重新认识node后端开发
查看>>
聊聊springboot session timeout参数设置
查看>>
微信小程序调研
查看>>
window下git多账户管理
查看>>
【327天】我爱刷题系列086(2017.12.29)
查看>>
React.js 小书 Lesson15 - 实战分析:评论功能(二)
查看>>
如何使用JSON和GSON
查看>>
weex脚手架
查看>>
js正则表达式学习
查看>>
C++ 开发 PHP 7 扩展之定义常量
查看>>
windows 命令行禁用密码策略,创建用户
查看>>
游戏小学生01-egret环境搭建
查看>>
从零开始写爬虫
查看>>
微信小程序,个人开发者创业新平台
查看>>