[ZJOI2006]三色二叉树 （树形dp）

题目描述

输入格式

输入文件名：TRO.IN

输入文件仅有一行，不超过500000个字符，表示一个二叉树序列。

输出格式

输出文件名：TRO.OUT

输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。

输入输出样例

输入 #1 

1122002010

输出 #1 

5 2

 解题报告

有人做不出好像是因为没读懂题？其实挺好懂的，把数组下标定义为从1开始，每个字符对应的就是他的儿子数，建树的过程就是dfs的过程。手动模拟一下就可以画出树了。

后面就很简单了，倒着递推，（应该没人会想不到这是个dp吧……）我感觉和美元汇率那道题有点像，只不过那个不是树就简单很多。

 

（分别是题目和样例的图示↓）

 

#include<bits/stdc++.h>
using namespace std;
const int N = 500100;
char s[N];
int son[N][2],dp[N][2],tot,len = 1;
void dfs(int x)
{   
    if(s[x] == '0')return ;
    if(s[x] == '1'){
        son[x][0] = ++len;
        dfs(son[x][0]);
    }
    if(s[x] == '2'){
        son[x][0] = ++len;
        dfs(son[x][0]);
        son[x][1] = ++len;
        dfs(len);
    } 
}
int main()
{
  scanf("%s",s + 1);
  int n = strlen(s+1);
  dfs(1);
  for(int i = n ; i > 0; i--){
      dp[i][1] = dp[son[i][0]][0] + dp[son[i][1]][0] + 1;  //父绿（bushi 
      dp[i][0] = max(dp[son[i][0]][1] + dp[son[i][1]][0],dp[son[i][0]][0] + dp[son[i][1]][1]);
      //左染绿右不染  和   左不染绿右染 
  }
  int maxn = max(dp[1][1],dp[1][0]); 
  cout << maxn << " " ;   
  
  for(int i = n ; i > 0; i--){
      dp[i][1] = dp[son[i][0]][0] + dp[son[i][1]][0] + 1;  
      dp[i][0] = min(dp[son[i][0]][1] + dp[son[i][1]][0],dp[son[i][0]][0] + dp[son[i][1]][1]);
  }
  int minn = min(dp[1][1],dp[1][0]); 
  cout << minn << " " ;
  return 0;
}