Description
Input
仅有一行,不超过500000个字符,表示一个二叉树序列。
Output
输出文件也只有一行,包含两个数,依次表示最多和最少有多少个点能够被染成绿色。
Sample Input
Sample Output
树形dp……
先讲最大值怎么求
令f[i][0]表示i这个点不染绿色,i下面的子树最多能取多少个绿色的点
f[i][1]表示i这个点染了绿色,i下面的子树最多能取多少个绿色的点
首先考虑对于一个点,如果染了绿色,那么根据题目所述,它的左右儿子必须染得跟它不一样,就是必须不是绿色
所以f[i][1]=f[r[i]][0]+f[l[i]][0]+1
然后如果这个点不染绿色,那么一个节点与其左右儿子必须颜色不同,就是说必须红绿蓝各一,那么还是只有一个绿色
枚举从左右儿子中哪一个转移过来就好了
所以f[i][0]=max(f[l[i]][0]+f[r[i]][1],f[l[i]][1]+f[r[i]][0])
最小值同理
#include<cstdio>
#define MAX 300010
int f[MAX][2];
int l[MAX],r[MAX];
int treesize=1;
inline int max(int a,int b)
{return a>b?a:b;}
inline int min(int a,int b)
{return a<b?a:b;}
inline void read(int now)
{
char ch=getchar();
if (ch=='0')return;
treesize++;l[now]=treesize;read(treesize);
if (ch=='2')
{
treesize++;
r[now]=treesize;
read(treesize);
}
}
inline void dp1(int now)
{
if (!now)return;
dp1(r[now]);dp1(l[now]);
f[now][1]=f[l[now]][0]+f[r[now]][0]+1;
f[now][0]=max(f[l[now]][0]+f[r[now]][1],f[l[now]][1]+f[r[now]][0]);
}
inline void dp2(int now)
{ if (!now)return;
dp2(r[now]);dp2(l[now]);
f[now][1]=f[l[now]][0]+f[r[now]][0]+1;
f[now][0]=min(f[l[now]][0]+f[r[now]][1],f[l[now]][1]+f[r[now]][0]);
}
int main()
{
read(1);
dp1(1);
printf("%d ",max(f[1][0],f[1][1]));
for (int i=1;i<=treesize;i++){f[i][0]=0;f[i][1]=0;}
dp2(1);
printf("%d\n",min(f[1][0],f[1][1]));
}
bzoj1864 [Zjoi2006]三色二叉树的更多相关文章
-
BZOJ1864[ZJOI2006]三色二叉树[树形DP]
1864: [Zjoi2006]三色二叉树 Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 773 Solved: 548[Submit][Status] ...
-
bzoj千题计划212:bzoj1864: [Zjoi2006]三色二叉树
http://www.lydsy.com/JudgeOnline/problem.php?id=1864 #include<cstdio> #include<cstring> ...
-
【题解】 bzoj1864: [Zjoi2006]三色二叉树 (动态规划)
bzoj1864,懒得复制,戳我戳我 Solution: 其实想出来了\(dp\)方程推出来了最大值,一直没想到推最小值 \(dp[i][1/0]\)表示\(i\)号节点的子树中的绿色染色最大值,\( ...
-
【BZOJ1864】[Zjoi2006]三色二叉树 树形DP
1864: [Zjoi2006]三色二叉树 Description Input 仅有一行,不超过500000个字符,表示一个二叉树序列. Output 输出文件也只有一行,包含两个数,依次表示最多和最 ...
-
嘴巴题5 「BZOJ1864」[ZJOI2006] 三色二叉树
1864: [Zjoi2006]三色二叉树 Time Limit: 1 Sec Memory Limit: 64 MB Submit: 1195 Solved: 882 [Submit][Status ...
-
【BZOJ-1864】三色二叉树 树形DP
1864: [Zjoi2006]三色二叉树 Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 659 Solved: 469[Submit][Status] ...
-
BZOJ 1864: [Zjoi2006]三色二叉树( 树形dp )
难得的ZJOI水题...DFS一遍就行了... ----------------------------------------------------------------------- #inc ...
-
BZOJ_1864_[Zjoi2006]三色二叉树_树形DP
BZOJ_1864_[Zjoi2006]三色二叉树_树形DP 题意: 分析:递归建树,然后DP,从子节点转移. 注意到红色和蓝色没有区别,因为我们可以将红蓝互换而方案是相同的.这样的话我们只需要知道当 ...
-
【BZOJ1864】三色二叉树(动态规划)
[BZOJ1864]三色二叉树(动态规划) 题面 BZOJ 题解 首先把树给构出来. 设\(f[i][0/1]\)表示当前节点\(i\),是否是绿色节点的子树中最大/最小的绿色节点的个数和. 转移很显 ...
随机推荐
-
1.GoldenGate 简单的一对一配置
一,软件安装 源端和目标端均执行(只要修改相应的目录) 1.上传软件,放到ogg的安装目录,并解压 mkdir /home/oracle/ogg unzip ogg112101_fbo_g ...
-
app令牌的一个token实现
app登陆验证不能使用session来判断了.然后查资料都说用令牌,没找到合适的方法,我的眼界太小.另外,越来越感觉基础的重要,比如,session是什么,我竟无言以对.不知道session是什么,怎 ...
-
ASP.NET中彩票项目中的计算复式投注的注数的方法
从别人做的项目中抽取出的代码:
-
[2014.5.22][UBUNTU]Ubuntu与Windows系统时间不同步的问题
安装Ubuntu+Windows双系统时会遇到Windows和Ubuntu系统时间不同步的问题,这是由于Windows系统默认读取主板bios等硬件系统时间作为OS的当地时间;而MAc,Linux类的 ...
-
Nginx配置域名跳转实例
要求:浏览器地址栏输入qj.123.com之后,地址自动变成qj.abc.com 配置nginx跳转 server { listen 80; server_name qj.abc.com qj.123 ...
-
秀才每天一篇之—SEO是什么?
[导读]SEO是什么?秀才搁笔七天以来.遇到非常多事情.站点被K ,排名掉了. 却找不出原因,開始迷茫了.以至于没有心情来照应这个博客,不好意思了,各位.在这七天以来.秀才一直在思考,SEO究竟应该怎 ...
-
寒哥细谈之AutoLayout全解
文/南栀倾寒(简书作者)原文链接:http://www.jianshu.com/p/683fbcbfb705著作权归作者所有,转载请联系作者获得授权,并标注“简书作者”. 看到群中好多朋友还停留在Fr ...
-
用javascript和html5做一个音乐播放器,附带源码
效果图: 实现的功能 1.首页 2.底部播放控件 3.播放页面 4.播放列表 5.排行榜 6.音乐搜索 输入搜索关键词,点击放大镜图标 7.侧边栏 目录结构 开发心得与总结 1.轮播图 首先感谢作者S ...
-
新版netkeeper开wifi无需路由器
谈一谈netkeeper的运行原理及如何不用路由器开启wifi.(针对重庆地区,其它地区没研究过.日期:2017.11.29) 旧版: netkeeper将用户名加密为真正的用户名进行登录,登录以后n ...
-
UNIX域协议之描述符传递
一.mycat程序 #include <fcntl.h> #include <stdlib.h> #include <unistd.h> #define BUFFS ...