BZOJ-1864-[Zjoi2006]三色二叉树（树形dp）

Description

Input

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

Output

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

Sample Input

1122002010

Sample Output

5 2

HINT

Source

Day1

题解

这道题我们考虑dp

我们先把树给构造出来（可以用栈，也可以用dfs）

建完树后，我们用f[i][0/1/2][0]表示i节点填绿/蓝/红色的最小答案，f[i][0/1/2][1]表示i节点填绿/蓝/红色的最大答案

我们考虑i节点从两个儿子转移

f[i][0][0]=min(f[s1][1][0]+f[s2][2][0],f[s1][2][0]+f[s2][1][0])

f[i][1][0]=min(f[s1][0][0]+f[s2][2][0],f[s1][2][0]+f[s2][0][0])

f[i][2][0]=min(f[s1][0][0]+f[s2][1][0],f[s1][1][0]+f[s2][0][0])

f[i][0/1/2][1]转移同理

 #include<bits/stdc++.h>

 #define N 500005

 using namespace std;

 int tot,top;

 int Stack[N];

 int f[N][][];

 char s[N];

 int main(){

     scanf("%s",s+);

     int len=strlen(s+);

     for (int i=len;i>=;i--)

         if (s[i]==''){

             int x=Stack[top],y=Stack[--top];

             tot++;

             f[tot][][]=min(f[x][][]+f[y][][],f[x][][]+f[y][][])+;

             f[tot][][]=min(f[x][][]+f[y][][],f[x][][]+f[y][][]);

             f[tot][][]=min(f[x][][]+f[y][][],f[x][][]+f[y][][]);

             f[tot][][]=max(f[x][][]+f[y][][],f[x][][]+f[y][][])+;

             f[tot][][]=max(f[x][][]+f[y][][],f[x][][]+f[y][][]);

             f[tot][][]=max(f[x][][]+f[y][][],f[x][][]+f[y][][]);

             Stack[top]=tot;

         } else

         if (s[i]==''){

             int x=Stack[top];

             tot++;

             f[tot][][]=min(f[x][][],f[x][][])+;

             f[tot][][]=min(f[x][][],f[x][][]);

             f[tot][][]=min(f[x][][],f[x][][]);

             f[tot][][]=max(f[x][][],f[x][][])+;

             f[tot][][]=max(f[x][][],f[x][][]);

             f[tot][][]=max(f[x][][],f[x][][]);

             Stack[top]=tot;

         } else{

             tot++;

             f[tot][][]=f[tot][][]=;

             Stack[++top]=tot;

         }

     int Max=max(f[tot][][],max(f[tot][][],f[tot][][]));

     int Min=min(f[tot][][],min(f[tot][][],f[tot][][]));

     printf("%d %d",Max,Min);

     return ;

 }

巴特西