삼색이차수---위조수형dp

제목 설명
한 그루의 두 갈래 나무는 다음과 같은 규칙에 따라 0, 1, 2로 구성된 문자 서열을 나타낼 수 있으며, 우리는'두 갈래 나무 서열 S'라고 부른다.
0 이 나무는 하위 노드가 없습니다. 1S1 이 나무는 하위 노드가 있습니다. S1은 두 갈래 나무 서열입니다. 1S1S2 이 나무는 두 개의 하위 노드가 있습니다. S1, S2는 각각 두 갈래 나무의 서열입니다. 예를 들어 아래 그림에 표시된 두 갈래 나무는 두 갈래 나무 서열 S=2200110으로 표시할 수 있습니다.
너의 임무는 두 갈래 나무의 노드를 염색하는 것이다.각 노드는 빨간색, 녹색, 파란색으로 염색할 수 있다.그리고 하나의 노드와 그 하위 노드의 색깔은 반드시 달라야 한다. 만약에 이 노드가 두 개의 하위 노드가 있다면 이 두 개의 하위 노드의 색깔도 같지 않아야 한다.두 갈래 나무의 두 갈래 나무 서열을 정하고 이 나무 중 가장 많고 적어도 몇 개의 점이 녹색으로 물들 수 있는지 요청합니다.
제목 대의:
너에게 나무 한 그루를 줄게, 서로 다른 색깔, 모두 세 가지 색깔로, 한 가지 색깔을 가장 적게 칠하는 방법을 구해라.분석:
제목 조건에 따라 열 이동 방정식:
성질세 가지 색깔이 있기 때문에 아버지 노드가 녹색이 아니라면 두 아들 중 하나는 녹색이다.쓸데없는 소리
성질만약 부모 노드가 녹색이라면, 두 하위 노드는 반드시 모두 녹색이 아니며, 충돌하지 않을 것이다.(쓸데없는 말2)
우리는 두 가지 상황(새로운 차원)을 설정해도 무방하다. dp[rt][0]는 rt점이 녹색이 아니라는 것을 나타내고, dp[rt][1]는 녹색을 나타내며, dp수조의 값은 이 점을 루트로 하는 나무가 최대 몇 개의 녹색점을 칠한다는 것을 나타낸다.우리는 모든 노드에 초기 값을 설정할 수 있습니다: dp[rt][0]=0, dp[rt][1]=1(이해하시죠...)
이동 방정식: 1.dp[ rt ][ 1]=dp[ lch[ rt ] ] [ 0 ]+dp[ rch[ rt ] ] [ 0 ]+1;
이 점 녹색 칠하기 상황: 왼쪽 아들이 녹색을 칠하지 않는 상황 + 오른쪽 아들이 녹색을 칠하지 않는 상황 + 자신;
(이 점을 녹색으로 칠하면 좌우 두 점을 모두 녹색으로 칠할 수 없고 이런 좌우 두 점이 충돌하지 않는 상황은 반드시 존재한다. 즉, 성질2)
　　　　　2.dp[ rt ][ 0 ]=min/max ( dp[ lch[ rt ] ] [ 0 ]+dp[ rch[ rt ] ] [ 1 ]  ,  dp[ lch[ rt ] ] [ 1]+dp[ rch[ rt ] ] [ 0 ] );
이 점은 녹색을 칠하지 않는 경우: 왼쪽 아들은 녹색을 칠하지 않고, 오른쪽 아들은 녹색을 칠하거나 왼쪽 아들은 녹색을 칠하지 않으며, 오른쪽 아들은 녹색을 칠하지 않는다.
(또한 필연적인 조건, 상기 성질에 부합1)
그리고 dfs입니다.
코드:

#include
#include
#include
#include
#include
using namespace std;
const int maxn=1e6+10;
char s[maxn];int a[maxn];
int cnt=1;// dfs ， 1 ， （ ） int lch[maxn],rch[maxn],dp[maxn][2];
void build(int rt){// ， ，  
    if(a[rt]==1){
        lch[rt]=++cnt;    
        build(lch[rt]);
    }else if(a[rt]==2){
        lch[rt]=++cnt;    
        build(lch[rt]);
        rch[rt]=++cnt;
        build(rch[rt]);
    }else if(a[rt]==0){
        return;
    }
}
void dfsmax(int rt){
    dp[rt][1]=1;dp[rt][0]=0;
    if(lch[rt])dfsmax(lch[rt]);
    if(rch[rt])dfsmax(rch[rt]);
    dp[rt][1]=1+dp[lch[rt]][0]+dp[rch[rt]][0];
    dp[rt][0]=max(dp[lch[rt]][1]+dp[rch[rt]][0],dp[lch[rt]][0]+dp[rch[rt]][1]);
    //  
}
void dfsmin(int x){
    dp[x][1]=1;dp[x][0]=0;
    if(lch[x]) dfsmin(lch[x]);
    if(rch[x]) dfsmin(rch[x]);
    dp[x][1]=1+dp[lch[x]][0]+dp[rch[x]][0];
    dp[x][0]=min(dp[lch[x]][1]+dp[rch[x]][0],dp[lch[x]][0]+dp[rch[x]][1]);
}
int main(){
    scanf("%s",s);
    int len=strlen(s);
    for(int i=0;i){
        a[i+1]=s[i]-'0';// ，  
    }
    build(1);
    dfsmax(1);// 1  
    printf("%d ",max(dp[1][1],dp[1][0]));//  
    memset(dp,0,sizeof(dp));// ！！！ 
    dfsmin(1);
    printf("%d ",min(dp[1][1],dp[1][0]));
    return 0;
}