1754.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1754 on 2006-03-03 at 21:15:16 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 1024;
const int INF = 1 << 30;

int main()
{
	int b, l, n, w[MAX], v[MAX];
	int i, j;
	double time[MAX];
	
	time[0] = 0;
	while(scanf("%d %d %d", &b, &l, &n) != EOF && b != 0) {
		for(i = 0; i < n; i++) {
			scanf("%d %d", &w[i], &v[i]); 
			int sum, speed = INF; time[i+1] = 1e10;
			for(sum = w[i], j = i; sum <= b && j >= 0; j--, sum += w[j]) {
				speed = min(speed, v[j]);
				time[i+1] = min(time[i+1], time[j]+l*1.0/speed);
			}
		}
		printf("%.1lf\n", time[n]*60);
	}
	
	return 0;
}