【BZOJ1864】三色二叉树（动态规划）
题面
题解
首先把树给构出来。
设\(f[i][0/1]\)表示当前节点\(i\)，是否是绿色节点的子树中最大/最小的绿色节点的个数和。
转移很显然。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 500500
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
char ch[MAX];
struct Line{int v,next;}e[MAX<<1];
int h[MAX],cnt=1,son[MAX];
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;++son[u];}
int pos=1,tot;
void Build(int nw)
{
if(ch[pos]=='0')return;
if(ch[pos]=='1')
{
++pos;Add(nw,++tot);Build(tot);
return;
}
else
{
++pos;Add(nw,++tot);Build(tot);
++pos;Add(nw,++tot);Build(tot);
return;
}
}
int f[MAX][2];
void dfs1(int u)
{
if(!son[u])f[u][0]=0,f[u][1]=1;
else if(son[u]==1)
{
int v=e[h[u]].v;
dfs1(v);
f[u][0]=max(f[v][0],f[v][1]);
f[u][1]=f[v][0]+1;
}
else
{
int v1=e[h[u]].v,v2=e[e[h[u]].next].v;
dfs1(v1);dfs1(v2);
f[u][0]=max(f[v1][0]+f[v2][1],f[v1][1]+f[v2][0]);
f[u][1]=f[v1][0]+f[v2][0]+1;
}
}
void dfs2(int u)
{
if(!son[u])f[u][0]=0,f[u][1]=1;
else if(son[u]==1)
{
int v=e[h[u]].v;
dfs2(v);
f[u][0]=min(f[v][0],f[v][1]);
f[u][1]=f[v][0]+1;
}
else
{
int v1=e[h[u]].v,v2=e[e[h[u]].next].v;
dfs2(v1);dfs2(v2);
f[u][0]=min(f[v1][0]+f[v2][1],f[v1][1]+f[v2][0]);
f[u][1]=f[v1][0]+f[v2][0]+1;
}
}
int main()
{
scanf("%s",ch+1);
Build(tot=1);
memset(f,0,sizeof(f));dfs1(1);printf("%d ",max(f[1][0],f[1][1]));
memset(f,0,sizeof(f));dfs2(1);printf("%d\n",min(f[1][0],f[1][1]));
return 0;
}