2247.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2247 on 2006-05-24 at 14:43:22 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int NM = 128;
const int DN = 8;
const double eps = 1e-5;
const double RATE = 0.85;
double SUM[DN] = { 0 };

class Unit {
public:
	bool dmg;
	int x, y, hp; 
	vector<int> nxt;
	void make() { nxt.clear(); dmg = false; scanf("%d %d %d", &x, &y, &hp); }
	bool jump(const Unit& u, int d) const { return (x-u.x)*(x-u.x)+(y-u.y)*(y-u.y) <= d*d; }
	bool operator <(const Unit& u) const { return u.hp < hp; }
};

Unit u[NM];
double best;
int n, jn;

void hurl(int, int, double, double);

int main()
{
	int d, i, j;
	double e = 1;
	
	for(i = 1; i < DN; i++) {
		e *= RATE;
		SUM[i] = SUM[i-1] + e;
	}
	while(scanf("%d %d", &d, &n) != EOF) {
		for(i = 0; i < n; i++) u[i].make();
		sort(u, u+n);
		for(i = 0; i < n; i++)
			for(j = i+1; j < n; j++)
				if(u[i].jump(u[j], d)) { u[i].nxt.push_back(j); u[j].nxt.push_back(i); }
		best = 0; jn = min(DN, n);
		for(i = 0; i < n; i++) hurl(i, 1, 180, 0);
		printf("%.3lf\n", best);
	}
	
	return 0;
}

void hurl(int o, int step, double prev, double total)
{
	u[o].dmg = true;
	double hurt = min(prev, (double)u[o].hp);
	total += hurt; best = max(best, total);
	if(step != jn && total+SUM[jn-step]*hurt-best > eps) {
		int i; hurt *= RATE;
		for(i = 0; i < u[o].nxt.size(); i++) {
			int no = u[o].nxt[i];
			if(u[no].dmg) continue;
			hurl(no, step+1, hurt, total);
		}
	}
	u[o].dmg = false;
}