Description
Input
仅有一行，不超过500000个字符，表示一个二叉树序列。
Output
输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。
Sample Input
1122002010
Sample Output
5 2
HINT
Source
题解
这道题我们考虑dp
我们先把树给构造出来（可以用栈，也可以用dfs）
建完树后，我们用f[i][0/1/2][0]表示i节点填绿/蓝/红色的最小答案，f[i][0/1/2][1]表示i节点填绿/蓝/红色的最大答案
我们考虑i节点从两个儿子转移
f[i][0][0]=min(f[s1][1][0]+f[s2][2][0],f[s1][2][0]+f[s2][1][0])
f[i][1][0]=min(f[s1][0][0]+f[s2][2][0],f[s1][2][0]+f[s2][0][0])
f[i][2][0]=min(f[s1][0][0]+f[s2][1][0],f[s1][1][0]+f[s2][0][0])
f[i][0/1/2][1]转移同理
#include<bits/stdc++.h>
#define N 500005
using namespace std;
int tot,top;
int Stack[N];
int f[N][][];
char s[N];
int main(){
scanf("%s",s+);
int len=strlen(s+);
for (int i=len;i>=;i--)
if (s[i]==''){
int x=Stack[top],y=Stack[--top];
tot++;
f[tot][][]=min(f[x][][]+f[y][][],f[x][][]+f[y][][])+;
f[tot][][]=min(f[x][][]+f[y][][],f[x][][]+f[y][][]);
f[tot][][]=min(f[x][][]+f[y][][],f[x][][]+f[y][][]);
f[tot][][]=max(f[x][][]+f[y][][],f[x][][]+f[y][][])+;
f[tot][][]=max(f[x][][]+f[y][][],f[x][][]+f[y][][]);
f[tot][][]=max(f[x][][]+f[y][][],f[x][][]+f[y][][]);
Stack[top]=tot;
} else
if (s[i]==''){
int x=Stack[top];
tot++;
f[tot][][]=min(f[x][][],f[x][][])+;
f[tot][][]=min(f[x][][],f[x][][]);
f[tot][][]=min(f[x][][],f[x][][]);
f[tot][][]=max(f[x][][],f[x][][])+;
f[tot][][]=max(f[x][][],f[x][][]);
f[tot][][]=max(f[x][][],f[x][][]);
Stack[top]=tot;
} else{
tot++;
f[tot][][]=f[tot][][]=;
Stack[++top]=tot;
}
int Max=max(f[tot][][],max(f[tot][][],f[tot][][]));
int Min=min(f[tot][][],min(f[tot][][],f[tot][][]));
printf("%d %d",Max,Min);
return ;
}