bzoj1864: [Zjoi2006]三色二叉树(树形DP)
2019-08-16 08:02:25来源:博客园 阅读 ()
bzoj1864: [Zjoi2006]三色二叉树(树形DP)
题目:
1864: [Zjoi2006]三色二叉树
解析:
用\(f[u][0/1/2]\)表示以\(u\)为根,颜色为绿/红/蓝时最多的数量
转移没啥好说的
\(f[u][0] = max(f[l][1] + f[r][2], f[l][2] + f[r][1]) + 1\)
\(f[u][1/2] = max(f[l][0] + f[r][2/1], f[l][2/1] + f[r][0])\)
最小值同理
建树的话递归建树就可以了
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 +10;
int n, m, num, rt;
int t[N][2], f[N][3];
char s[N];
inline void build(int &x) {
x = ++num;
if (s[x] == '0') return;
if (s[x] == '1') build(t[x][0]);
if (s[x] == '2') build(t[x][0]), build(t[x][1]);
}
void Max(int u) {
if (!u) return;
int l = t[u][0], r = t[u][1];
Max(l), Max(r);
f[u][0] = max(f[l][1] + f[r][2], f[l][2] + f[r][1]) + 1;
f[u][1] = max(f[l][0] + f[r][2], f[l][2] + f[r][0]);
f[u][2] = max(f[l][0] + f[r][1], f[l][1] + f[r][0]);
}
void Min(int u) {
if (!u) return;
int l = t[u][0], r = t[u][1];
Min(l), Min(r);
f[u][0] = min(f[l][1] + f[r][2], f[l][2] + f[r][1]) + 1;
f[u][1] = min(f[l][0] + f[r][2], f[l][2] + f[r][0]);
f[u][2] = min(f[l][0] + f[r][1], f[l][1] + f[r][0]);
}
int main() {
cin >> (s + 1);
build(rt);
Max(rt);
cout << max(f[rt][0], max(f[rt][1], f[rt][2])) << " ";
memset(f, 0, sizeof f);
Min(rt);
cout << min(f[rt][0], min(f[rt][1], f[rt][2]));
return 0;
}
原文链接:https://www.cnblogs.com/lykkk/p/11354294.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- bzoj1003: [ZJOI2006]物流运输(最短路+DP) 2019-08-16
- P1772 [ZJOI2006]物流运输 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash