BZOJ 1864:[Zjoi2006]三色二叉树(树DP)
2024-09-29 10:30:22
三色二叉树
问题描述
输入
仅有一行,不超过500000个字符,表示一个二叉树序列。
输出
输出文件也只有一行,包含两个数,依次表示最多和最少有多少个点能够被染成绿色。
样例输入
1122002010
样例输出
5 2
分析:简单树DP
program tree1;
var
f,g:array[..,..]of longint;
l,r:array[..]of longint;
n,i,m,x,y,sum,len:longint;
s:ansistring;
function max(x,y:longint):longint;
begin
if x>y then max:=x else max:=y;
end;
function min(x,y:longint):longint;
begin
if x<y then min:=x else min:=y;
end;
procedure dfs(x:longint);
var i:longint;
begin
inc(len); i:=len;
if s[i]='' then exit;
inc(sum); l[x]:=sum; dfs(sum);
if s[i]='' then
begin
inc(sum); r[x]:=sum; dfs(sum);
end;
end;
procedure dp(x:longint);
var i:longint;
begin
if x= then exit;
dp(l[x]); dp(r[x]);
f[x,]:=max(f[l[x],]+f[r[x],],f[l[x],]+f[r[x],])+;
f[x,]:=max(f[l[x],]+f[r[x],],f[l[x],]+f[r[x],]);
f[x,]:=max(f[l[x],]+f[r[x],],f[l[x],]+f[r[x],]);
g[x,]:=min(g[l[x],]+g[r[x],],g[l[x],]+g[r[x],])+;
g[x,]:=min(g[l[x],]+g[r[x],],g[l[x],]+g[r[x], ]);
g[x,]:=min(g[l[x],]+g[r[x],],g[l[x],]+g[r[x],]);
end;
begin
readln(s);n:=length(s); sum:=; len:=;
fillchar(l,sizeof(l),); fillchar(r,sizeof(r),);
dfs(); dp();
x:=max(max(f[,],f[,]),f[,]);
y:=min(min(g[,],g[,]),g[,]);
writeln(x,' ',y);
end.
最新文章
- ASP.NET Core HTTP 管道中的那些事儿
- linux搭建LAMP
- 【图像】Matlab图像标定工具箱
- Android下常见的四种对话框
- ASP.NET MVC路由配置(转载自http://www.cnblogs.com/zeusro/p/RouteConfig.html )
- 【转】IOS --- OC与Swift混编
- 实时监控mysql数据库变化
- 基于visual Studio2013解决算法导论之049活动选择问题
- [Windwos Phone] 实作地图缩放 MapAnimationKind 属性效果
- Openjudge-计算概论(A)-苹果和虫子
- Vue 2.x + Webpack 3.x + Nodejs 多页面项目框架(上篇——纯前端多页面)
- labview与单片机串口通信
- idea注册码
- Spring框架基础(下)
- Linux的基础命令
- Spring 快速开始 配置Spring Framework
- Python学习之旅(一)
- Day7作业及默写
- iOS 覆盖率检测原理与增量代码测试覆盖率工具实现
- 嗜血法医第八季/全集Dexter 8迅雷下载
热门文章
- ARM体系结构与编程-3
- empty、isset、is
- 为什么L1稀疏,L2平滑?
- CUDA:Supercomputing for the Masses (用于大量数据的超级计算)-第一节
- AJAX进行分页
- vue列表过渡效果
- 2019 ACM-ICPC全国邀请赛(西安) M.Travel 二分+判联通
- 使用paramiko报错:CryptographyDeprecationWarning: Support for unsafe construction of public numbers from encoded data will be removed in a future version. Please use EllipticCurvePublicKey.from_encoded_poi
- python3 包的发布
- 将Excel文件转为csv文件的python脚本