比赛 |
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;
}