[BZOJ] 물문제 1864 삼색 두 갈래 나무.

BZOJ 1864 삼색 두 갈래 나무
 
직관적인 느낌은 비교적 어렵다. 왜냐하면 이전의 나무에 염색한 것이 나를 놀라게 하고 오랫동안 생각했기 때문이다.
 
먼저 한 걸음 한 걸음 문제를 해결하고, 읽는 것은 하나의 어려움이다. 표현열을 나무로 바꾸는 것을 어떻게 해결할 것인가?
 
'1S1'이든'2S1S2'이든 모두 왼쪽 나무가 있는 것을 발견했고 샘플을 살펴보면 왼쪽 나무가 처리된 후에야 오른쪽 나무를 처리한다는 것을 알 수 있다.그래서 차례로 나무를 세울 수 있습니다. 두 갈래 나무이기 때문에 ls와rs수로 좌우 아들을 저장하면 됩니다.
 
그러면 어떻게 녹색으로 염색하는 최대치를 구합니까?DP를 생각하다.한 가지 색깔만 염색하면 되기 때문에, 우리는 이 점이 녹색으로 염색되었는지 주목하면 된다!
 
상태 dp 정의(u, 0/1):
 
dp(u,1)는 이 점이 녹색으로 염색되었다는 것을 나타낸다. 그러면 자나무는 반드시 다른 색깔일 것이다. 아들이 어떤 색깔로 염색되었는지 신경 쓸 필요가 없다.그래서 전이 방정식 1:
dp(u,1)= dp(ls ( u),0)+ dp(rs ( u),0)+ 1;
 
dp(u,0)는 이 점이 녹색으로 염색되지 않았다는 것을 나타낸다. 그러면 나무는 반드시 하나는 녹색으로 염색되고 다른 하나는 다른 색으로 염색된다. 단지 우리는 도대체 어느 것이 어떤 색으로 염색되었는지 모른다.걱정하지 마세요. 왼쪽 아들이 녹색으로 염색되었거나 오른쪽 아들이 녹색으로 염색되었을 때 우리는 이 두 가지 상황에 대해 최소치(또는 최대치(필요에 따라 녹색으로 염색된 최치를 결정)만 취하면 이동 방정식을 얻을 수 있습니다.
                                     dp(ls (u),1)+ dp(rs ( u),0)
dp(u,0) min/max
                                     dp(ls (u),0)+ dp(rs ( u),1)
 
코드:

/**************************************************************
    Problem: 1864
    User: jerrywans
    Language: C++
    Result: Accepted
    Time:328 ms
    Memory:29028 kb
****************************************************************/
 
#include 
 
const  int  N = 500000 + 5 ; 
 
int  dp [ N << 2 ] [ 3 ] , ls [ N ] , rs [ N ] ;
int  tail = 1 ;
 
int  minx ( int  a , int  b ) {
    return  a < b ? a : b ; 
}
 
int  maxx ( int  a , int  b ) {
    return  a > b ? a : b ; 
}
 
void  build ( int  x ) {
    char  c ;
    scanf ( "%c" , &c ) ;
    if ( c == '0' )  return ;
    ls [ x ] = ++ tail ;
    build ( ls [ x ] ) ;
    if ( c == '2' ) {
        rs [ x ] = ++ tail ;
        build ( rs [ x ] ) ;
    }
}
 
void  dfs ( int  u , int  opt ) {
    if ( !u )  return  ;
    dfs ( ls [ u ] , opt ) ;
    dfs ( rs [ u ] , opt ) ;
     
    dp [ u ] [ 1 ] = dp [ ls [ u ] ] [ 0 ] + dp [ rs [ u ] ] [ 0 ] + 1 ; 
    if ( opt == 1 )
        dp [ u ] [ 0 ] = maxx ( dp [ ls [ u ] ] [ 1 ] + dp [ rs [ u ] ] [ 0 ] , dp [ ls [ u ] ] [ 0 ] + dp [ rs [ u ] ] [ 1 ] ) ;
    else
        dp [ u ] [ 0 ] = minx ( dp [ ls [ u ] ] [ 1 ] + dp [ rs [ u ] ] [ 0 ] , dp [ ls [ u ] ] [ 0 ] + dp [ rs [ u ] ] [ 1 ] ) ;
}
 
int  main ( ) {
    build ( 1 ) ;
    dfs ( 1 , 1 ) ;
    printf ( "%d " , maxx ( dp [ 1 ] [ 0 ] , dp [ 1 ] [ 1 ] ) ) ;
    memset ( dp , 0 , sizeof ( dp ) ) ;
    dfs ( 1 , 2 ) ;
    printf ( "%d" , minx ( dp [ 1 ] [ 0 ] , dp [ 1 ] [ 1 ] ) ) ;
     
    return  0 ;
}