bzoj 1864: [Zjoi2006]三色二叉树

Description

solution

正解：递归+树型DP
我们首先递归建树
然后考虑树型DP，我们设绿色的节点为Y，非绿色为N
我们神奇的发现：N会形成是很多条相互独立的链
也就是说 Y 的下发有两个 N，这两个N一定可以不同，因为此题是二叉树，可以手推出
所以DP状态只需表示为 (f[i][N/Y])
(f[i][Y]=f[ls][N]+f[rs][N]+1)
(f[i][N]=Max(f[ls][Y]+f[rs][N],f[rs][Y]+f[ls][N]))
第二问改成Min即可

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=500005;
char S[N];int n,ch[N][2],t=1,cnt=0,root;
void dfs(int &x){
   x=++cnt;
   if(S[t]=='2'){
      t++;dfs(ch[x][0]);
      t++;dfs(ch[x][1]);
   }
   else if(S[t]=='1')t++,dfs(ch[x][0]);
}
int f[N],g[N];
void hxy(int x,bool t){
   if(ch[x][0])hxy(ch[x][0],t);
   if(ch[x][1])hxy(ch[x][1],t);
   int ls=ch[x][0],rs=ch[x][1];
   f[x]=g[ls]+g[rs]+1;
   if(!t)g[x]=Max(g[ls]+f[rs],f[ls]+g[rs]);
   else g[x]=Min(g[ls]+f[rs],f[ls]+g[rs]);
}
void work()
{
   scanf("%s",S+1);n=strlen(S+1);
   dfs(root);hxy(root,0);
   printf("%d ",Max(f[1],g[1]));
   hxy(root,1);
   printf("%d
",Min(f[1],g[1]));
}

int main()
{
	work();
	return 0;
}