bzoj1864 [Zjoi2006]三色二叉树

时间:2021-07-30 16:35:00

Description

bzoj1864 [Zjoi2006]三色二叉树

Input

仅有一行,不超过500000个字符,表示一个二叉树序列。

Output

输出文件也只有一行,包含两个数,依次表示最多和最少有多少个点能够被染成绿色。

Sample Input

1122002010


Sample Output

5 2

树形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]三色二叉树的更多相关文章

  1. BZOJ1864&lbrack;ZJOI2006&rsqb;三色二叉树&lbrack;树形DP&rsqb;

    1864: [Zjoi2006]三色二叉树 Time Limit: 1 Sec  Memory Limit: 64 MBSubmit: 773  Solved: 548[Submit][Status] ...

  2. bzoj千题计划212:bzoj1864&colon; &lbrack;Zjoi2006&rsqb;三色二叉树

    http://www.lydsy.com/JudgeOnline/problem.php?id=1864 #include<cstdio> #include<cstring> ...

  3. 【题解】 bzoj1864&colon; &lbrack;Zjoi2006&rsqb;三色二叉树 (动态规划)

    bzoj1864,懒得复制,戳我戳我 Solution: 其实想出来了\(dp\)方程推出来了最大值,一直没想到推最小值 \(dp[i][1/0]\)表示\(i\)号节点的子树中的绿色染色最大值,\( ...

  4. 【BZOJ1864】&lbrack;Zjoi2006&rsqb;三色二叉树 树形DP

    1864: [Zjoi2006]三色二叉树 Description Input 仅有一行,不超过500000个字符,表示一个二叉树序列. Output 输出文件也只有一行,包含两个数,依次表示最多和最 ...

  5. 嘴巴题5 「BZOJ1864」&lbrack;ZJOI2006&rsqb; 三色二叉树

    1864: [Zjoi2006]三色二叉树 Time Limit: 1 Sec Memory Limit: 64 MB Submit: 1195 Solved: 882 [Submit][Status ...

  6. 【BZOJ-1864】三色二叉树 树形DP

    1864: [Zjoi2006]三色二叉树 Time Limit: 1 Sec  Memory Limit: 64 MBSubmit: 659  Solved: 469[Submit][Status] ...

  7. BZOJ 1864&colon; &lbrack;Zjoi2006&rsqb;三色二叉树&lpar; 树形dp &rpar;

    难得的ZJOI水题...DFS一遍就行了... ----------------------------------------------------------------------- #inc ...

  8. BZOJ&lowbar;1864&lowbar;&lbrack;Zjoi2006&rsqb;三色二叉树&lowbar;树形DP

    BZOJ_1864_[Zjoi2006]三色二叉树_树形DP 题意: 分析:递归建树,然后DP,从子节点转移. 注意到红色和蓝色没有区别,因为我们可以将红蓝互换而方案是相同的.这样的话我们只需要知道当 ...

  9. 【BZOJ1864】三色二叉树(动态规划)

    [BZOJ1864]三色二叉树(动态规划) 题面 BZOJ 题解 首先把树给构出来. 设\(f[i][0/1]\)表示当前节点\(i\),是否是绿色节点的子树中最大/最小的绿色节点的个数和. 转移很显 ...

随机推荐

  1. 1&period;GoldenGate 简单的一对一配置

    一,软件安装   源端和目标端均执行(只要修改相应的目录)   1.上传软件,放到ogg的安装目录,并解压   mkdir /home/oracle/ogg unzip ogg112101_fbo_g ...

  2. app令牌的一个token实现

    app登陆验证不能使用session来判断了.然后查资料都说用令牌,没找到合适的方法,我的眼界太小.另外,越来越感觉基础的重要,比如,session是什么,我竟无言以对.不知道session是什么,怎 ...

  3. ASP&period;NET中彩票项目中的计算复式投注的注数的方法

    从别人做的项目中抽取出的代码:

  4. &lbrack;2014&period;5&period;22&rsqb;&lbrack;UBUNTU&rsqb;Ubuntu与Windows系统时间不同步的问题

    安装Ubuntu+Windows双系统时会遇到Windows和Ubuntu系统时间不同步的问题,这是由于Windows系统默认读取主板bios等硬件系统时间作为OS的当地时间;而MAc,Linux类的 ...

  5. Nginx配置域名跳转实例

    要求:浏览器地址栏输入qj.123.com之后,地址自动变成qj.abc.com 配置nginx跳转 server { listen 80; server_name qj.abc.com qj.123 ...

  6. 秀才每天一篇之—SEO是什么?

    [导读]SEO是什么?秀才搁笔七天以来.遇到非常多事情.站点被K ,排名掉了. 却找不出原因,開始迷茫了.以至于没有心情来照应这个博客,不好意思了,各位.在这七天以来.秀才一直在思考,SEO究竟应该怎 ...

  7. 寒哥细谈之AutoLayout全解

    文/南栀倾寒(简书作者)原文链接:http://www.jianshu.com/p/683fbcbfb705著作权归作者所有,转载请联系作者获得授权,并标注“简书作者”. 看到群中好多朋友还停留在Fr ...

  8. 用javascript和html5做一个音乐播放器,附带源码

    效果图: 实现的功能 1.首页 2.底部播放控件 3.播放页面 4.播放列表 5.排行榜 6.音乐搜索 输入搜索关键词,点击放大镜图标 7.侧边栏 目录结构 开发心得与总结 1.轮播图 首先感谢作者S ...

  9. 新版netkeeper开wifi无需路由器

    谈一谈netkeeper的运行原理及如何不用路由器开启wifi.(针对重庆地区,其它地区没研究过.日期:2017.11.29) 旧版: netkeeper将用户名加密为真正的用户名进行登录,登录以后n ...

  10. UNIX域协议之描述符传递

    一.mycat程序 #include <fcntl.h> #include <stdlib.h> #include <unistd.h> #define BUFFS ...