比赛 20090916练习赛 评测结果 AWAAWAAAAA
题目名称 护卫队 最终得分 80
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-09-21 20:18:23
显示代码纯文本
#include <cstdio>
#include <cstring>

using namespace std;

struct {
	int W;
	double T;
} rw[5001];
int sumw[5001];
double dym[5001];

int main ()
{
	freopen("convoy.in", "r", stdin);
	freopen("convoy.out", "w", stdout);
	
	int W, L, N;
	scanf("%d%d%d", &W, &L, &N);

	for (int i=1; i<=N; i++)
	{
		int S;
		scanf("%d%d", &(rw[i].W), &S);
		rw[i].T = (double)L/(double)S*60.0;
		if (i)
			sumw[i] = sumw[i-1] + rw[i].W;
	}

	for (int i=1; i<=N; i++)
	{
		dym[i] = 1E20;
		double maxt = 0.0;
		for (int j=1; j<=i && sumw[i]-sumw[i-j]<=W; j++)
		{
			double tmp;
			if (rw[i-j+1].T > maxt)
				maxt = rw[i-j+1].T;
			if ((tmp = dym[i-j] + maxt) < dym[i])
				dym[i] = tmp;
		}
	}

	printf("%.1lf\n", dym[N]);

	return 0;
}