比赛 20090916练习赛 评测结果 RRRRRRRRRR
题目名称 护卫队 最终得分 0
用户昵称 王者自由 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-09-21 19:33:18
显示代码纯文本
#include <cstdio>
const int MAXN = 1000;
int w, s, n;
int W[MAXN], S[MAXN];
double t, l, f[MAXN];
int main() {
	freopen("concoy.in", "r", stdin);
	freopen("concoy.out", "w", stdout);
	scanf("%d %d %d", &w, &s, &n);
	for(int i=1; i<=n; i++)
		scanf("%d %d", W+i, S+i);
	for(int i=1; i<=n; i++) {
		t = W[i];
		l = S[i];
		f[i] = f[i-1] + s / l;
		for(int j=i-1; j>=0; j--) {
			if(t > w)
				break;
			if(f[i] > f[j] + s / l)
				f[i] = f[j] + s / l;
			t += W[j];
			if(l > S[j])
				l = S[j];
		}
	}
	printf("%0.1lf\n", f[n] * 60);
	return 0;
}