BZOJ-1078: [SCOI2008]斜堆

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1078

发现某一个子树的序列可以由左右子树合并得到，那么就恶心的分类讨论一下合并的方案即可。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
 
using namespace std ;
 
const int maxn = 110 ;
 
int left[ maxn ] , right[ maxn ] , n ; 
 
inline vector < int > dfs( int now ) {
    vector < int > l , r , t ; 
    l.clear(  ) , r.clear(  ) , t.clear(  ) ;
    if ( left[ now ] ) l = dfs( left[ now ] ) ;
    if ( right[ now ] ) r = dfs( right[ now ] ) ;
    if ( ! l.size(  ) && ! r.size(  ) ) {
        t.push_back( now ) ;
    } else if ( ! r.size(  ) ) {
        if ( l.size(  ) > 1 ) {
            t.push_back( now ) ;
            for ( int i = 0 ; i < l.size(  ) ; ++ i ) t.push_back( l.at( i ) ) ;
        } else t.push_back( l.at( 0 ) ) , t.push_back( now ) ;
    } else {
        int i , j ; 
        for ( i = 0 , j = 0 ; i < l.size(  ) && j < r.size(  ) ; ++ i , ++ j ) {
            t.push_back( l.at( i ) ) ; t.push_back( r.at( j ) ) ;
        }
        if ( i < l.size(  ) ) {
            if ( i == l.size(  ) - 1 ) {
                t.push_back( l.at( i ) ) ;
                t.push_back( now ) ;
            } else {
                t.push_back( now ) ;
                for ( ; i < l.size(  ) ; ++ i ) t.push_back( l.at( i ) ) ;
            }
        } else if ( j < r.size(  ) ) {
            t.pop_back(  ) ;
            t.push_back( now ) ;
            for ( -- j ; j < r.size(  ) ; ++ j ) t.push_back( r.at( j ) ) ;
        } else t.push_back( now ) ;
    }
    return t ; 
}
 
int main(  ) {
    memset( left , 0 , sizeof( left ) ) , memset( right , 0 , sizeof( right ) ) ;
    scanf( "%d" , &n ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        int d ; scanf( "%d" , &d ) ;
        if ( d >= 100 ) right[ d - 100 ] = i ; else left[ d ] = i ; 
    }
    vector < int > ans = dfs( 0 ) ;
    for ( int i = ans.size(  ) - 1 ; i >= 0 ; -- i ) printf( "%d " , ans.at( i ) ) ;
    printf( "\n" ) ;
    return 0 ; 
}