题目描述
输入输出格式
输入格式：
输入文件名：TRO.IN
输入文件仅有一行，不超过10000个字符，表示一个二叉树序列。
输出格式：
输出文件名：TRO.OUT
输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。
输入输出样例
输入样例#1：
1122002010
输出样例#1： 
View Code
5 2 似乎已经很久没有写博客了 今天是noip2017初赛，离noip2017复赛还有不到一个月，我要加油做题了！ 题解： 首先得能通过输入的一串树把树的形态搞出来。自己模拟模拟后发现这个“二叉树序列”跟dfs差不多，用一个dfs就知道树是什么样的了。 在dfs时记录该节点有几个子节点（只可能是0、1、2），顺便记下子节点的编号。 之后计算最多最少几个节点被染成绿色就可以用dp了 至于问什么会想到dp呢？我猜是一个经验问题吧。 一开始想起来虽觉得不好算，但大问题可以转化为子问题后解决。对于每一个小部分求出最值后进一步求出稍大一部分的最值。 由于要求最大值与最小值，所以我用了两个dp数组。 dp[i][k]表示第i号节点的颜色为k，它与它子树中颜色为绿的的最大值。（在前面的dfs中根据dfs序可知每一个子树中的节点编号连续，且根节点是最小的） 转移方程有些长，直接看下面代码吧，懒得再写一遍了。 方程基本就是对于该节点的一种状态求出子节点可能的不同状态（状态数并不多）中的最值。 之后就可以啦 总结一下思路： 弄清楚“二叉树序列”的本质 -> 发现大问题难以求解，但可通过子问题计算出 -> 进行dp 注意：题目很坑，数据范围是有问题的，最多可能输入长度为500000 代码：
1 #include2 #include 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 }