首页 > 代码库 > BZOJ1864[ZJOI2006]三色二叉树[树形DP]
BZOJ1864[ZJOI2006]三色二叉树[树形DP]
1864: [Zjoi2006]三色二叉树
Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 773 Solved: 548
[Submit][Status][Discuss]
Description
Input
仅有一行,不超过500000个字符,表示一个二叉树序列。
Output
输出文件也只有一行,包含两个数,依次表示最多和最少有多少个点能够被染成绿色。
Sample Input
1122002010
Sample Output
5 2
HINT
Source
Day1
先建树
d[i][0/1]表示以i为根的子树i绿色1其他0下最多几个点绿色
三个颜色转移就是父子三人两个其他一个绿色
见代码
/************************************************************** Problem: 1864 User: thwfhk Language: C++ Result: Accepted Time:68 ms Memory:13884 kb****************************************************************/#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=5e5+5,INF=1e9;int n,mx=-INF,mn=INF;char s[N];struct node{ int ls,rs; node():ls(0),rs(0){}}tree[N];int cnt=0,pos=1;int build(){ int u=++cnt,num=s[pos]-‘0‘; pos++; if(num>=1) tree[u].ls=build(); if(num==2) tree[u].rs=build(); return u;}int d[N][2],f[N][2];void dp(int u){//printf("dp %d\n",u); if(u==0) return; int ls=tree[u].ls,rs=tree[u].rs; dp(ls);dp(rs); d[u][0]=max(d[ls][0]+d[rs][1],d[ls][1]+d[rs][0]); f[u][0]=min(f[ls][0]+f[rs][1],f[ls][1]+f[rs][0]); d[u][1]=d[ls][0]+d[rs][0]+1; f[u][1]=f[ls][0]+f[rs][0]+1;}int main(int argc, const char * argv[]) { scanf("%s",s+1); n=strlen(s+1); build(); dp(1); mx=max(d[1][0],d[1][1]); mn=min(f[1][0],f[1][1]); printf("%d %d",mx,mn); return 0;}
BZOJ1864[ZJOI2006]三色二叉树[树形DP]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。