M_sea

洛谷2585 [ZJOI2006]三色二叉树
题目描述传送门算法首先是读入,getchar()大法+递归就行了。。。然后是DP。设$f[i][0/1]$表示以i...
扫描右侧二维码阅读全文
27
2018/02

洛谷2585 [ZJOI2006]三色二叉树

题目描述

Problem

传送门

算法

首先是读入,getchar()大法+递归就行了。。。

然后是DP。
设$f[i][0/1]$表示以i为根的子树在i为/不为绿色时的最大绿色节点数。
那么$f[i][1]=f[lson][0]+f[rson][0]+1$,$f[i][0]=max(f[lson][1]+f[rson][0],f[lson][0]+f[rson][1])$

最小是类似的,太显然不解释。。。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;
struct Tree_Node {
    int l,r;
    Tree_Node() { this->l=this->r=0; }
}a[500010];
int n=1;
inline void build(int u) {
    char c=getchar();
    int op=c-'0';
    if (op==0) return;
    else if (op==1) { a[u].l=++n; build(a[u].l); }
    else if (op==2) { a[u].l=++n; build(a[u].l); a[u].r=++n; build(a[u].r); }
}
int f[500010][2]; //f[i][0/1]表示以i为根的子树在i为/不为绿色时的最大/最小绿色节点数 
inline void Dfs1(int u) {
    if (!u) return;
    Dfs1(a[u].l); Dfs1(a[u].r);
    f[u][1]=f[a[u].l][0]+f[a[u].r][0]+1;
    f[u][0]=max(f[a[u].l][0]+f[a[u].r][1],f[a[u].l][1]+f[a[u].r][0]);
}
inline void Dfs2(int u) {
    if (!u) return;
    Dfs2(a[u].l); Dfs2(a[u].r);
    f[u][1]=f[a[u].l][0]+f[a[u].r][0]+1;
    f[u][0]=min(f[a[u].l][0]+f[a[u].r][1],f[a[u].l][1]+f[a[u].r][0]);
}
int main() {
    build(1);
    Dfs1(1); printf("%d ",max(f[1][0],f[1][1]));
    memset(f,0,sizeof(0));
    Dfs2(1); printf("%d\n",min(f[1][0],f[1][1]));
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 39 PM

发表评论