2311.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2311 on 2006-08-07 at 16:40:58 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 10;
const int S = 1 << N;
const int INF = 1 << 30;

int n, s, c[N], best[S];
int tran[S], at[S], bt[S], tn, an, bn;

int find(int);

int main()
{
	int i, j, t, T;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		int a, b; scanf("%d %d %d", &n, &a, &b);
		for(i = 0; i < n; i++) scanf("%d", &c[i]);
		tn = an = bn = 0;
		s = 1 << n;
		for(i = 0; i < s; i++) {
			int w = 0;
			for(j = 0; j < n; j++)
				if(i&(1<<j)) w += c[j];
			if(w <= a) at[an++] = i;
			if(w <= b) bt[bn++] = i;
		}
		for(i = 0; i < s; i++) best[i] = INF;
		for(i = 0; i < an; i++)
			for(j = 0; j < bn; j++)
				best[at[i]|bt[j]] = 1;
		best[0] = 0;
		for(i = 0; i < s; i++)
			if(best[i] == 1) tran[tn++] = i;
		printf("Scenario #%d:\n%d\n\n", t+1, find(s-1));
	}
	
	return 0;
}

int find(int s)
{
	if(best[s] < INF) return best[s];
	int i, mb = INF;
	for(i = 0; i < tn; i++) {
		int cs = tran[i];
		if((s|cs) != s) continue;
		mb = min(mb, find(s^cs));
		if(mb == 1) break;
	}
	best[s] = mb+1;
	return best[s];
}