BZOJ1864[ZJOI2006]三色二叉树[树形DP]

1864: [Zjoi2006]三色二叉树

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 773  Solved: 548
[Submit][Status][Discuss]

Description

Input

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

Output

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

Sample Input

1122002010

Sample Output

5 2

HINT

Source

Day1

---

先建树

d[i][0/1]表示以i为根的子树i绿色1其他0下最多几个点绿色

三个颜色转移就是父子三人两个其他一个绿色

见代码

/**************************************************************
    Problem: 1864
    User: thwfhk
    Language: C++
    Result: Accepted
    Time:68 ms
    Memory:13884 kb
****************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e5+,INF=1e9;
int n,mx=-INF,mn=INF;
char s[N];
struct node{
    int ls,rs;
    node():ls(),rs(){}
}tree[N];
int cnt=,pos=;
int build(){
    int u=++cnt,num=s[pos]-'';
    pos++;
    if(num>=) tree[u].ls=build();
    if(num==) tree[u].rs=build();
    return u;
}
int d[N][],f[N][];
void dp(int u){//printf("dp %d\n",u);
    if(u==) return;
    int ls=tree[u].ls,rs=tree[u].rs;
    dp(ls);dp(rs);
    d[u][]=max(d[ls][]+d[rs][],d[ls][]+d[rs][]);
    f[u][]=min(f[ls][]+f[rs][],f[ls][]+f[rs][]);
    d[u][]=d[ls][]+d[rs][]+;
    f[u][]=f[ls][]+f[rs][]+;
}
int main(int argc, const char * argv[]) {
    scanf("%s",s+);
    n=strlen(s+);
    build();
    dp();
    mx=max(d[][],d[][]);
    mn=min(f[][],f[][]);
    printf("%d %d",mx,mn);
    return ;
}