题目描述
输入输出格式
输入格式：
输入文件名：TRO.IN
输入文件仅有一行，不超过10000个字符，表示一个二叉树序列。
输出格式：
输出文件名：TRO.OUT
输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。
输入输出样例
输入样例#1：
1122002010
输出样例#1：
5 2似乎已经很久没有写博客了今天是noip2017初赛，离noip2017复赛还有不到一个月，我要加油做题了！题解：首先得能通过输入的一串树把树的形态搞出来。自己模拟模拟后发现这个“二叉树序列”跟dfs差不多，用一个dfs就知道树是什么样的了。在dfs时记录该节点有几个子节点（只可能是0、1、2），顺便记下子节点的编号。之后计算最多最少几个节点被染成绿色就可以用dp了至于问什么会想到dp呢？我猜是一个经验问题吧。一开始想起来虽觉得不好算，但大问题可以转化为子问题后解决。对于每一个小部分求出最值后进一步求出稍大一部分的最值。由于要求最大值与最小值，所以我用了两个dp数组。dp[i][k]表示第i号节点的颜色为k，它与它子树中颜色为绿的的最大值。（在前面的dfs中根据dfs序可知每一个子树中的节点编号连续，且根节点是最小的）转移方程有些长，直接看下面代码吧，懒得再写一遍了。方程基本就是对于该节点的一种状态求出子节点可能的不同状态（状态数并不多）中的最值。之后就可以啦总结一下思路：弄清楚“二叉树序列”的本质 -> 发现大问题难以求解，但可通过子问题计算出 -> 进行dp注意：题目很坑，数据范围是有问题的，最多可能输入长度为500000代码：
1 #include<cstdio>
2 #include<iostream>
3 using namespace std;
4
5 const int MAXN=
500005;
6 int sonnum[MAXN],son[MAXN][
2];
7 int num=
0,root;
8
9 char ch;
10 void input(
int u){
11 sonnum[u]=ch-
'0';
12 if(ch-
'0'==
0)
return;
13 else if(ch-
'0'==
1){
14 son[u][
0]=++
num;
15 ch=
getchar();
16 input(num);
17 }
18 else{
19 son[u][
0]=++
num;
20 ch=
getchar();
21 input(num);
22 son[u][
1]=++
num;
23 fa[num]=
u;
24 ch=
getchar();
25 input(num);
26 }
27 }
28 int dp[MAXN][
3],dp2[MAXN][
3];
29
30 int main()
31 {
32 int i,j,x;
33 ch=
getchar();
34 while(ch<
'0' || ch>
'9') ch=
getchar();
35
36 root=++
num;
37 input(root);
38
39 for(i=num;i>
0;i--
){
40 if(sonnum[i]==
0){
41 dp[i][
0]=
1;
42 dp[i][
1]=dp[i][
2]=
0;
43
44 dp2[i][
0]=
1;
45 dp2[i][
1]=dp2[i][
2]=
0;
46 }
47 else if(sonnum[i]==
1){
48 dp[i][
0]=max(dp[son[i][
0]][
1],dp[son[i][
0]][
2])+
1;
49 dp[i][
1]=max(dp[son[i][
0]][
0],dp[son[i][
0]][
2]);
50 dp[i][
2]=max(dp[son[i][
0]][
0],dp[son[i][
0]][
1]);
51
52 dp2[i][
0]=min(dp2[son[i][
0]][
1],dp2[son[i][
0]][
2])+
1;
53 dp2[i][
1]=min(dp2[son[i][
0]][
0],dp2[son[i][
0]][
2]);
54 dp2[i][
2]=min(dp2[son[i][
0]][
0],dp2[son[i][
0]][
1]);
55 }
56 else {
57 dp[i][
0]=max(dp[son[i][
0]][
1]+dp[son[i][
1]][
2],dp[son[i][
0]][
2]+dp[son[i][
1]][
1])+
1;
58 dp[i][
1]=max(dp[son[i][
0]][
0]+dp[son[i][
1]][
2],dp[son[i][
0]][
2]+dp[son[i][
1]][
0]);
59 dp[i][
2]=max(dp[son[i][
0]][
0]+dp[son[i][
1]][
1],dp[son[i][
0]][
1]+dp[son[i][
1]][
0]);
60
61 dp2[i][
0]=min(dp2[son[i][
0]][
1]+dp2[son[i][
1]][
2],dp2[son[i][
0]][
2]+dp2[son[i][
1]][
1])+
1;
62 dp2[i][
1]=min(dp2[son[i][
0]][
0]+dp2[son[i][
1]][
2],dp2[son[i][
0]][
2]+dp2[son[i][
1]][
0]);
63 dp2[i][
2]=min(dp2[son[i][
0]][
0]+dp2[son[i][
1]][
1],dp2[son[i][
0]][
1]+dp2[son[i][
1]][
0]);
64 }
65 }
66 printf(
"%d ",max(dp[
1][
0],max(dp[
1][
1],dp[
1][
2])));
67 printf(
"%d\n",min(dp2[
1][
0],min(dp2[
1][
1],dp2[
1][
2])));
68 return 0;
69 }
View Code
转载于:https://www.cnblogs.com/lindalee/p/7668824.html
相关资源：数据结构—成绩单生成器
