嘴巴题5 「BZOJ1864」[ZJOI2006] 三色二叉树
2024-08-25 21:29:55
1864: [Zjoi2006]三色二叉树
Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 1195 Solved: 882
[Submit][Status][Discuss]
Description
Input
仅有一行,不超过500000个字符,表示一个二叉树序列。
Output
输出文件也只有一行,包含两个数,依次表示最多和最少有多少个点能够被染成绿色。
Sample Input
1122002010
Sample Output
5 2
HINT
Source
Day1
题解
我们发现交换蓝色和红色方案仍然合法。而题目中关注绿色个数,当绿色确定后,其他点的颜色依次可以填出,所以只需dp绿色即可。
以最小为例
\(dp[i][0/1]\)表示i点不是/是绿色的子树最小绿色数
转移:
\[dp[i][0] = min(dp[lson[i]][1] + dp[lson[i]][0], dp[rson[i][0]] + dp[rson[i]][1])\]
\[dp[i][1] = dp[lson[i]][0] + dp[rson[i]][0] + 1\]
最新文章
- 在Visual Studio 中开发自定义脚手架 Scaffolder
- IOS 学习笔记之UI
- 聚合数据全国天气预报api接口
- memcached学习(5). memcached的应用和兼容程序
- Javascript-显示系统时间
- struts2中使用ognl表达式时各种符号的使用规则$,#,%
- Apache JMeter开源压力测试/负载测试工具 2.12 官方最新版
- 如何修改vsftpd的默认根目录/var/ftp/pub到另一个目录?
- memcache的原理和命中率的总结
- 在CUDA8.0下编译安装OpenCV3.1.0来实现GPU加速(Compiling OpenCV3.1.0 with CUDA8.0 support)
- IntelliJ IDEA下Maven SpringMVC+Mybatis入门搭建例子
- 学习css之选择器优先级
- “百度杯”CTF比赛 2017 二月场_onthink
- ActivityLifecycleCallbacks 的简单使用
- vue插件
- yum 安装时遇到“UnicodeDecodeError: 'ascii' codec”的问题
- [转] babel 教程
- ichartjs一分钟快速入门教程
- Mac下的命令行自动补全功能
- 函数使用三:采购过账BAPI_GOODSMVT_CREATE