pku2767.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <algorithm>
using namespace std;

typedef struct Bowl
{
	double h, r, R;
}Bowl;

Bowl b[9];
double H[9][9]; //把B在A上面 
int N;
int p[9];

double get_total()
{
	int i, j;
	double hh[10], max;
	for (i = 0; i < N; i++)
	{
		hh[i] = 0;
		for (j = i - 1; j >= 0; j--)
		{
			if (hh[j] + H[p[j]][p[i]] > hh[i])
				hh[i] = hh[j] + H[p[j]][p[i]];
		}
	}
	max = 0;
	for (i = 0; i < N; i++)
	{
		hh[i] += b[p[i]].h;
		if (hh[i] > max)
			max = hh[i];
	}
	return max;
}

double get_H(double h, double r, double R, double rx)
{
	if (rx >= R)
		return h;
	if (rx <= r)
		return 0;
	return (rx - r) * h / (R - r);
}

double Calc(const Bowl &X, const Bowl &Y)
{
	double ans = 0;
	double tmp;
	tmp = get_H(X.h,X.r,X.R,Y.r);
	if (tmp > ans)
		ans = tmp;
	tmp = get_H(X.h,X.r,X.R,Y.R) - Y.h;
	if (tmp > ans)
		ans = tmp;
	if (X.R < Y.R)
	{	tmp = X.h - get_H(Y.h,Y.r,Y.R,X.R);
		if (tmp > ans)
			ans = tmp;
	}
	return ans;	
}

void Solve()
{
	int i, j;
	double tmp, max;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%lf %lf %lf", &b[i].h, &b[i].r, &b[i].R);
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			if (i == j)
				continue;
			H[i][j] = Calc(b[i], b[j]);
		}
	}
	for (i = 0; i < N; i++)
		p[i] = i;
	max = 1e30;
	do
	{
		tmp = get_total();
		if (tmp < max)
			max = tmp;
	}while(next_permutation(p, p + N));
	printf("%d\n", (int)max);
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
		Solve();
	return 0;
}