TREE
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495
#include <bits/stdc++.h>
using namespace std;
#define MAX 10005
using namespace std;
int Max[MAX][3], Min[MAX][3], id;
typedef struct T_Node{
struct T_Node * left;
struct T_Node * right;
int data;
}node;
node* getTree(string str){
char cnt=str[id];
node *root=new node;
root->data=id;
id++;
if(cnt=='2'){
root->left=getTree(str);
root->right=getTree(str);
}else if(cnt=='1'){
root->left=getTree(str);
root->right=NULL;
}else{
root->left=NULL;
root->right=NULL;
}
return root;
}
int solMax(node *root,int col){
if(root==NULL){
return 0;
}
if(Max[root->data][col]!=-1){
return Max[root->data][col];
}
int ans = col==2?1:0;
if(col==2){
ans += max(solMax(root->left,1)+solMax(root->right,0),
solMax(root->left,0)+solMax(root->right,1));
}else if(col==1){
ans += max(solMax(root->left,0)+solMax(root->right,2),
solMax(root->left,2)+solMax(root->right,0));
}else{
ans += max(solMax(root->left,1)+solMax(root->right,2),
solMax(root->left,2)+solMax(root->right,1));
}
Max[root->data][col]=ans;
return ans;
}
int solMin(node *root,int col){
if(root==NULL){
return 0;
}
if(Min[root->data][col]!=-1){
return Min[root->data][col];
}
int ans = col==2 ? 1:0;
if(col==2){
ans += min(solMin(root->left,1)+solMin(root->right,0),
solMin(root->left,0)+solMin(root->right,1));
}else if(col==1){
ans += min(solMin(root->left,0)+solMin(root->right,2),
solMin(root->left,2)+solMin(root->right,0));
}else{
ans += min(solMin(root->left,1)+solMin(root->right,2),
solMin(root->left,2)+solMin(root->right,1));
}
Min[root->data][col]=ans;
return ans;
}
// 0-Red, 1-Blue, 2-Green
// trau bo vl
int main(){
freopen("COLORING.inp", "r", stdin);
freopen("COLORING.out", "w", stdout);
string st;
cin>>st;
id=0;
for(int i = 0; i < st.length(); i ++){
for (int j = 0; j < 3; j ++) Max[i][j] = Min[i][j] = -1;
}
node* root = getTree(st);
int l_Max = max(solMax(root, 0), max(solMax(root, 1),solMax(root, 2)));
int l_Min = min(solMin(root, 0), min(solMin(root, 1),solMin(root, 2)));
cout << l_Max << " " << l_Min;
}
Cpp
INFO