3855 - 三色二叉树

1122002010

5 2

Solution C++

#define lson(x) (tree[x].lson)
#define rson(x) (tree[x].rson)

#define MAXN 10010UL
#define MAXC 3UL
#define MAXS 2UL

#include <cstdio>
#include <cstring>

struct BTree{
	int lson,rson;
};

BTree tree[MAXN];
int f[MAXN][MAXC][MAXS],node_cnt=1,p;
char s[MAXN];

inline int MAX(int a,int b){return a>b?a:b;}
inline int MIN(int a,int b){return a<b?a:b;}

//0->RED
//1->GREEN
//2->BLUE
//0->MIN
//1->MAX

void Build(int now_node){
	if(s[p]=='0') p++;
	else if(s[p]=='1') p++,lson(now_node)=++node_cnt,Build(node_cnt);
	else p++,lson(now_node)=++node_cnt,Build(node_cnt),rson(now_node)=++node_cnt,Build(node_cnt);
	return;
}

void tree_dp(int t){
	int ls=lson(t),rs=rson(t);
	if(ls) tree_dp(ls);
	if(rs) tree_dp(rs);
	if((!ls)&&(!rs)){//none
		f[t][0][0]=0;//red min
		f[t][1][0]=1;//green min
		f[t][2][0]=0;//blue min
		f[t][0][1]=0;//red max
		f[t][1][1]=1;//green max
		f[t][2][1]=0;//blue max
	}
	else if(!rs){//only
		f[t][0][0]=MIN(f[ls][1][0],f[ls][2][0]);//red min
		f[t][1][0]=1+MIN(f[ls][0][0],f[ls][2][0]);//green min
		f[t][2][0]=MIN(f[ls][0][0],f[ls][1][0]);//blue min
		f[t][0][1]=MAX(f[ls][1][1],f[ls][2][1]);//red max
		f[t][1][1]=1+MAX(f[ls][0][1],f[ls][2][1]);//green max
		f[t][2][1]=MAX(f[ls][0][1],f[ls][1][1]);//blue max
	}
	else{//all have
		f[t][0][0]=0x2fffffff;
		f[t][1][0]=0x2fffffff;
		f[t][2][0]=0x2fffffff;
		f[t][0][1]=0;
		f[t][1][1]=0;
		f[t][2][1]=0;
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				for(int k=0;k<3;k++){
					if(i==j||j==k||i==k) continue;
					int op=f[ls][j][0]+f[rs][k][0];
					if(i==1) op++;
					if(op<f[t][i][0]) f[t][i][0]=op;
				}
			}
		}
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				for(int k=0;k<3;k++){
					if(i==j||j==k||i==k) continue;
					int op=f[ls][j][1]+f[rs][k][1];
					if(i==1) op++;
					if(op>f[t][i][1]) f[t][i][1]=op;
				}
			}
		}		
	}
	return;
}

int main(){
	scanf("%s",s+1);
	p=1;Build(1);tree_dp(1);
	int Ans1=MAX(MAX(f[1][0][1],f[1][1][1]),f[1][2][1]);
	int Ans2=MIN(MIN(f[1][0][0],f[1][1][0]),f[1][2][0]);
	printf("%d %d\n",Ans1,Ans2);
	return 0;
}