2933.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2933  User Id:fzk 
Memory:48K  Time:779MS
Language:C++  Result:Accepted

Source 

#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( "%d\n", maxs );
	return 0;
}