i.cpp

ACM大赛基本练习题

#include <stdio.h>

#define MAXN 32
#define MASK 17
#define MAX 32768

const int mask[MASK] = { 0, 1, 2, 4, 8, 16, 32, 64, 128,
		256, 512, 1024, 2048, 4096, 8192, 16384, 32768 };

int minLeft, total;
int n, m;
int left[MAX];
int dat[MAXN];
int used[MAXN];

void ready()
{
	int i, j;

	left[0] = 0;
	left[1] = 1;

	for( i = 2; i < MAX; ++i )
		for( j = 0; j < MASK; ++j )
			if( i <= mask[j] )
			{
				left[i] = mask[j] - i;
				break;
			}
}

void read_dat()
{
	int i;

	scanf( "%d %d", &n, &m );
	total = 0;
	m = n - m - 1;
	minLeft = mask[MASK - 1];

	for( i = 0; i < n; ++i )
	{
		scanf( "%d", &dat[i] );
		used[i] = 0;
		total += dat[i];
	}
}

void search_it( int pre, int p, int s, int nows, int nowLeft, int t )
{
	int tmp, i;

	if( nowLeft >= minLeft || n - t + p <= m || p == n )
		return;

	if( p >= m )
	{
		tmp = nowLeft + left[nows] + left[total - s];
		if( tmp <= minLeft )
			minLeft = tmp;
	}

	for( i = 0; i < n && used[i]; ++i );

	if( i < n )
	{
		used[i] = 1;
		search_it( i, p + 1, s + dat[i], dat[i], nowLeft + left[nows], t + 1 );
		used[i] = 0;
	}

	if( p > 0 )
	{
		for( i = pre + 1; i < n; ++i )
			if( !used[i] )
			{
				used[i] = 1;
				search_it( i, p, s + dat[i], nows + dat[i], nowLeft, t + 1 );
				used[i] = 0;
			}
	}
}

int main()
{
	int i, testCase;

	scanf( "%d", &testCase );
	ready();

	for( i = 0; i < testCase; ++i )
	{
		read_dat();
		search_it( -1, 0, 0, 0, 0, 0 );
		printf( "%d\n", minLeft );
	}

	return 0;
}