1740.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1740 on 2006-02-19 at 22:48:56 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 32;
const int LIMIT = 420;

class Museum {
public:
	int t, o;
	void make(int);
	bool operator <(const Museum&) const;
};
void Museum::make(int co) {
	scanf("%d", &t); o = co;
}
bool Museum::operator <(const Museum& m) const {
	return t < m.t;
}

Museum m[MAX];
int n, vn, road[MAX][MAX];
bool vst[MAX];

void walk(int, int, int);

int main()
{
	int i, j, to[MAX];
	
	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 0; i < n; i++) m[i].make(i);
		sort(m, m+n);
		for(i = 0; i < n; i++) to[m[i].o] = i;
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++) scanf("%d", &road[to[i]][to[j]]);
		vn = 0; int l = n;
		for(n = 0; n < l && m[n].t <= LIMIT; n++) ;
		for(i = 0; i < n; i++) {
			memset(vst, false, sizeof(vst));
			vst[i] = true; walk(m[i].t, i, 1); vst[i] = false;
		}
		printf("%d\n", vn);
	}
	
	return 0;
}

void walk(int time, int b, int d)
{
	vn = max(d, vn);
	int i, mt = time, md = d;
	for(i = 0; i < n; i++)
		if(!vst[i] && mt+m[i].t <= LIMIT) mt += m[i].t, md++;
	if(md <= vn) return;
	for(i = 0; i < n; i++) {
		if(vst[i]) continue;
		int ct = time + m[i].t + road[b][i];
		if(ct <= LIMIT) { vst[i] = true; walk(ct, i, d+1); vst[i] = false; }
	}
}