http://www.lydsy.com/JudgeOnline/problem.php?id=1864
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; #define N 500001 char s[N]; int root;
int tr[N][]; int m;
int g[N][],f[N][]; void dfs(int &rt)
{
rt=++m;
int tmp=s[m]-'';
if(!tmp) return;
dfs(tr[rt][]);
if(tmp>) dfs(tr[rt][]);
} void DP(int rt)
{
if(!rt) return;
int l=tr[rt][],r=tr[rt][];
DP(l); DP(r);
int x,y,z;
for(int i=;i<;++i)
{
x=(i+)%; y=(x+)%; z= i ? : ;
g[rt][i]=max(g[l][x]+g[r][y],g[l][y]+g[r][x])+z;
f[rt][i]=min(f[l][x]+f[r][y],f[l][y]+f[r][x])+z;
}
} int main()
{
scanf("%s",s+);
dfs(root);
DP(root);
printf("%d ",max(g[root][],max(g[root][],g[root][])));
printf("%d",min(f[root][],max(f[root][],f[root][])));
}
1864: [Zjoi2006]三色二叉树
Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 1146 Solved: 844
[Submit][Status][Discuss]
Description
Input
仅有一行,不超过500000个字符,表示一个二叉树序列。
Output
输出文件也只有一行,包含两个数,依次表示最多和最少有多少个点能够被染成绿色。
Sample Input
1122002010
Sample Output
5 2