时间限制: 1 s 空间限制: 128000 KB
题目描述 Description
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
输入描述 Input Description
第一行D1 C D2 P N
之后N行，每行2个数表示离出发点的距离Di和每升汽油的价格Pi
输出描述 Output Description
最消费用，保留2位小数
样例输入 Sample Input
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
样例输出 Sample Output
26.95
数据范围及提示 Data Size & Hint
N<=100
代碼實現：
#include<iostream>
#include<cstdio>
using namespace std;
double d[],p[],cd,cl,zh,my,zhc,yl=;
int n;
void hx(int x){
if(x==n+) return;
double hc=;
int a=x,b=x+,pd=;
do{
++a;
hc=d[a]-d[x];
if(a==n+) break;
}while(hc<=zh);
for(int i=x+;i<a;i++){
b=i;
if(p[i]<p[x]&&i<=n+) {pd=;break;}
}
my+=(d[b]-d[x]-yl)*p[x];
if(pd) {yl=zh-d[b]+d[x];my+=yl*p[x];}
else yl=;
hx(b);
}
int main(){
scanf("%lf%lf%lf%lf%d",&zhc,&cl,&cd,&p[],&n);
zh=cd*cl;d[n+]=zhc;
for(int i=;i<=n;i++){
cin>>d[i]>>p[i];
if(d[i]-d[i-]>zh){
printf("No Solution");
return ;
}
}
hx();
printf("%.2lf\n",my/cd);
return ;
}
之前做過，直接粘的。。。