# 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;
}

```
This entry was posted in poj. Bookmark the permalink.