比赛 |
NOIP_2 |
评测结果 |
AAWWWWWWWW |
题目名称 |
驾车旅行 |
最终得分 |
20 |
用户昵称 |
BYVoid |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2008-09-08 22:22:20 |
显示代码纯文本
#include <iostream>
#define MAX 100
#define min(a,b) (a)<(b)?(a):(b)
using namespace std;
double Distance,MaxL,Cost;
double V[MAX],F[MAX],S[MAX];
int N;
void init()
{
int i;
freopen("tour.in","r",stdin);
freopen("tour.out","w",stdout);
cin >> Distance >> MaxL >> Cost >> F[0] >> N;
for (i=1;i<=N;i++)
cin >> S[i] >> V[i];
}
void solve()
{
int i,k;
double Dis;
for (i=1;i<=N;i++)
{
F[i]=0x7FFFFFF;
for (k=0;k<=i-1;k++)
{
Dis=(S[i]-S[k]) / Cost;
if (Dis >= MaxL / 2 && Dis <= MaxL)
F[i]=min(F[i],F[k]+ Dis * V[i] +20);
}
}
F[N+1]=0x7FFFFFF;
for (k=1;k<=N;k++)
{
Dis=(Distance-S[k]) / Cost;
if (Dis <= MaxL)
F[N+1]=min(F[N+1],F[k]+ Dis * V[k]);
}
printf("%.1lf",F[N]);
}
int main()
{
init();
solve();
return 0;
}