Poj Solution 2933

http://poj.org/problem?id=2933

#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
using namespace std;

int a[30];
int in[15];
int de[15];
int n, maxs;

bool search( int k, int im, int dm ) {
    int i, t;
    if( k >= n )
        return true;
    for( i=0; i<im; i++ ) {
        if( in[i] <= a[k] ) {
            t = in[i];
            in[i] = a[k];
            if( search( k+1, im, dm ) )
                return true;
            in[i] = t;
        }
    }
    
    for( i=0; i<dm; i++ ) {
        if( de[i] >= a[k] ) {
            t = de[i];
            de[i] = a[k];
            if( search( k+1, im, dm ) )
                return true;
            de[i] = t;
        }
    }
    
    if( im+dm < maxs ) {
        in[im] = a[k];
        if( search( k+1, im+1, dm ) )
            return true;
        de[dm] = a[k];
        if( search( k+1, im, dm+1 ) )
            return true;
    }
    return false;
}

int main( ) {
    int i;

    scanf( "%d", &n );
    for( i=0; i<n; i++ )
        scanf( "%d", a+i );
    for( maxs=1; maxs<=n/2; maxs++ )
        if( search( 0, 0, 0 ) )
            break;
    if( maxs > n/2 )
        maxs = 0;
    printf( "%dn", maxs );
    return 0;
}