P2585 [ZJOI2006]三色二叉树

P2585 [ZJOI2006]三色二叉树

一道奇奇怪怪的动规，可以递推的树形动规。

输入比较奇葩，考虑递归建树。

对于有2个孩子的情况，可以看看遍历了几个节点，然后加一就是编号。

void build(int l) {
    if(l>n)return;
    ++tot;
    if(s[l]=='0')return;
    if(s[l]=='1') {
        g[l].push_back(l+1);
        build(l+1);
    }
    if(s[l]=='2') {
        g[l].push_back(l+1);
        build(l+1);
        g[l].push_back(tot+1);
        build(tot+1);
    }
}

DP可以直接递推。dp[u][0]表示不染绿，dp[u][1]表示染绿。

dp[u][0]的时候，想想就发现它的左右孩子至少一个绿的。然后枚举。

dp[u][1]的时候，2个孩子不是绿的。

//1：染绿，0：不染绿 
int f(int x,int y,int o) {
    if(!o) return x>y?x:y;
    else return x<y?x:y;
}
void DP(int o) {
    for(int i=n;i>=1;--i) {
        int x=0,y=0;
        if(g[i].size()>0)x=g[i][0];
        if(g[i].size()>1)y=g[i][1];
        dp[i][0]=f(dp[x][1]+dp[y][0],dp[x][0]+dp[y][1],o);
        dp[i][1]=dp[x][0]+dp[y][0]+1;
    }
}

Code

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
char s[N];
int n,tot,dp[N][2];//1：染绿，0：不染绿 
vector<int>g[N];
void build(int l) {
    if(l>n)return;
    ++tot;
    if(s[l]=='0')return;
    if(s[l]=='1') {
        g[l].push_back(l+1);
        build(l+1);
    }
    if(s[l]=='2') {
        g[l].push_back(l+1);
        build(l+1);
        g[l].push_back(tot+1);
        build(tot+1);
    }
}
int f(int x,int y,int o) {
    if(!o) return x>y?x:y;
    else return x<y?x:y;
}
void DP(int o) {
    for(int i=n;i>=1;--i) {
        int x=0,y=0;
        if(g[i].size()>0)x=g[i][0];
        if(g[i].size()>1)y=g[i][1];
        dp[i][0]=f(dp[x][1]+dp[y][0],dp[x][0]+dp[y][1],o);
        dp[i][1]=dp[x][0]+dp[y][0]+1;
    }
}
int main() {
    scanf("%s",s+1);
    n=strlen(s+1);
    build(1);
    DP(0);
    printf("%d ",f(dp[1][1],dp[1][0],0));
    DP(1);
    printf("%d\n",f(dp[1][1],dp[1][0],1));
    return 0;
}

P2585 [ZJOI2006]三色二叉树

原文：https://www.cnblogs.com/zzctommy/p/12416387.html