2291.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2291 on 2006-07-26 at 13:07:20 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 9;

class Bowl {
public:
	double r, R, h, k;
	void make() { scanf("%lf %lf %lf", &h, &r, &R); k = h/(R-r); }
	double stack(const Bowl&) const;
};
double Bowl::stack(const Bowl& b) const {
	if(r >= b.R) return b.h;
	else {
		double ch = min(h, b.h);
		if(r <= b.r && ch/k+r <= ch/b.k+b.r) return 0;
		double d1 = 0, d2 = 0, d3 = 0;
		if(R < b.R) d1 = b.k*(R-b.r)-h;
		if(R > b.R) d2 = b.h-k*(b.R-r);
		if(r > b.r) d3 = b.k*(r-b.r);
		return max(d1, max(d2, d3));
	}
}

double bh[N][N];

int main()
{
	Bowl b[N];
	int stkn[N], n;
	int t, T, i, j;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n);
		for(i = 0; i < n; i++) { b[i].make(); stkn[i] = i; }
		double best = 1e25, tbh[N];
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				if(i != j) bh[i][j] = b[i].stack(b[j]);
		do {
			double top = 0;
			for(i = 0; i < n; i++) {
				tbh[i] = 0;
				for(j = 0; j < i; j++)
					tbh[i] = max(tbh[i], tbh[j]+bh[stkn[i]][stkn[j]]);
			}
			for(i = 0; i < n; i++)
				top = max(top, tbh[i]+b[stkn[i]].h);
			best = min(best, top);
		} while(next_permutation(stkn, stkn+n));
		printf("%.0lf\n", floor(best));
	}
	
	return 0;
}