【BZOJ 1864】 [Zjoi2006]三色二叉树

1864: [Zjoi2006]三色二叉树Time Limit:1 SecMemory Limit:64 MBSubmit:481Solved:321[Submit][Status][Discuss]Description

Input

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

Output

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

Sample Input

1122002010

Sample Output

5 2

HINTSource

Day1

dp。

根据字符串dfs，分别求最大最小即可。

a[x].f[0]表示x这个点是红色，他的子孙们符合条件的最大值;f[1]表示绿色;f[2]表示蓝色;

a[x].g[]表示最小。

#include <iostream>#include <cstring>#include <cmath>#include <algorithm>#include <cstdio>#define M 500000+5using namespace std;char s[M];int tot=1,f[M];struct tree{int f[3],g[3];}a[M];void dfs(int x){int son[3];son[0]=s[x]-'0';for (int i=1;i<=son[0];i++)son[i]=++tot,dfs(tot);for (int i=0;i<=2;i++){int ans1=0,ans2=0;int c1,c2;if (i==0) c1=1,c2=2;if (i==1) ans1=ans2=1,c1=0,c2=2;if (i==2) c1=0,c2=1;if (son[0]==2)ans1=ans1+max(a[son[1]].f[c1]+a[son[2]].f[c2],a[son[1]].f[c2]+a[son[2]].f[c1]),ans2=ans2+min(a[son[1]].g[c1]+a[son[2]].g[c2],a[son[1]].g[c2]+a[son[2]].g[c1]);if (son[0]==1)ans1=ans1+max(a[son[1]].f[c1],a[son[1]].f[c2]),ans2=ans2+min(a[son[1]].g[c1],a[son[1]].g[c2]);a[x].f[i]=ans1;a[x].g[i]=ans2;}}int main(){scanf("%s",1+s);a[0].f[0]=a[0].f[1]=a[0].f[2]=0;dfs(1);cout<<max(a[1].f[0],max(a[1].f[1],a[1].f[2]))<<" ";cout<<min(a[1].g[0],min(a[1].g[1],a[1].g[2]))<<endl;return 0;}

懂得接受失败的人，就是懂得人生真谛的人，