题目大意
一棵二叉树可以按照如下规则表示成一个由$0,1,2$组成的字符序列，我们称之为“二叉树序列$S$”：
例如，下图所表示的二叉树可以用二叉树序列$S=21200110$来表示。
你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。
题目分析
先按照题意建出树，然后进行树形动规。
先求最大值。
设$f[i]$为当前结点染成绿色的最大答案，$g[i]$为不染成绿色的最大答案。
求最小值把$\max$改成$\min$即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=500005;
int f[maxn],g[maxn],Left[maxn],Right[maxn];
void TreeDp1(int Now) {
if(Left[Now])TreeDp1(Left[Now]);
if(Right[Now])TreeDp1(Right[Now]);
f[Now]=g[Left[Now]]+g[Right[Now]]+1;
g[Now]=max(f[Left[Now]]+g[Right[Now]],g[Left[Now]]+f[Right[Now]]);
}
void TreeDp2(int Now) {
if(Left[Now])TreeDp2(Left[Now]);
if(Right[Now])TreeDp2(Right[Now]);
f[Now]=g[Left[Now]]+g[Right[Now]]+1;
g[Now]=min(f[Left[Now]]+g[Right[Now]],g[Left[Now]]+f[Right[Now]]);
}
char s[maxn];
int n;
stack<int>S;
int main() {
scanf("%s",s);
n=strlen(s);
for(int i=1; i<=n; i++) {
if(!S.empty()) {
if(Left[S.top()])Right[S.top()]=i;
else Left[S.top()]=i;
S.pop();
}
for(int j=1; j<=s[i-1]-'0'; j++)S.push(i);
}
TreeDp1(1);
printf("%d ",max(f[1],g[1]));
TreeDp2(1);
printf("%d ",min(f[1],g[1]));
return 0;
}
|
