2346.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 2346 on 2006-09-23 at 03:25:41 */
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 128;

double v, e, f, b;
int r;

double spend(int);

int main()
{
	int n, x[N];
	double cost[N][N], best[N];
	
	while(scanf("%d", &n) != EOF && n != 0) {
		for(int i = 1; i <= n; i++) scanf("%d", &x[i]);
		n++; x[0] = 0;
		scanf("%lf %d %lf %lf %lf", &b, &r, &v, &e, &f);
		for(int i = 0; i < n; i++)
			for(int j = i; j < n; j++)
				if(j == i) cost[i][i] = 0;
				else {
					cost[i][j] = cost[i][j-1];
					for(int k = x[j-1]; k < x[j]; k++) cost[i][j] += spend(k-x[i]);
				}
		best[0] = -b;
		for(int i = 1; i < n; i++) {
			best[i] = 1e50;
			for(int j = i-1; j >= 0; j--) 
				best[i] <?= best[j]+b+cost[j][i];
		}
		printf("%.4lf\n", best[n-1]);
	}
	
	return 0;
}

double spend(int x)
{
	if(x >= r) return 1/(v-e*(x-r));
	else return 1/(v-f*(r-x));
}