BZOJ 1864: [ZJOI2006]三色二叉树 – [树形DP]


题目传送门(BZOJ)
>原文链接<

题解 :

这是一道非常基础的树形DP。

读入部分递归的去初始化每个节点。

状态 : F[i][0/1]代表i节点选或不选绿色的最大/最小方案数(分别求一遍)

转移 : F[i][1] =F[ls][0]+F[rs][0]+1 F[i][0] = \max(F[ls][0]+F[rs][1], F[rs][0]+F[ls][1])

求最小值把\max换成\min即可

答案是\max(F[1][0], F[1][1])

代码 :

#include 
#include 
#include 
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)
#define rep(i, a, b) for(int i = a; i <= b; i ++ )
char buf[100000],*p1,*p2;
const int N = 510000;
int n = 1, ch[N][2];
#define ls ch[p][0]
#define rs ch[p][1]
int f[N][2], ans1, ans2;
void init(int p) {
    int siz = nc()^48;
    for(int i = 0; i < siz; i ++ ) ch[p][i] = ++n, init(n);
}
void dfs1(int p) {
    if(!p) return ;
    dfs1(ls), dfs1(rs);
    f[p][1] = f[ls][0]+f[rs][0]+1;
    f[p][0] = std :: max(f[ls][0]+f[rs][1], f[rs][0]+f[ls][1]);
}
void dfs2(int p) {
    if(!p) return ;
    dfs2(ls), dfs2(rs);
    f[p][1] = f[ls][0]+f[rs][0]+1;
    f[p][0] = std :: min(f[ls][0]+f[rs][1], f[rs][0]+f[ls][1]);
}
int main() {
    init(1);
    dfs1(1); ans1 = std :: max(f[1][0], f[1][1]);
    memset(f, 0, sizeof f);
    dfs2(1); ans2 = std :: min(f[1][0], f[1][1]);
    printf("%d %d\n", ans1, ans2);
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注