旅行规划问题

G 先生想独自驾驶汽车从城市A 到城市B。从城市A 到城市B 的距离为d0 公里。汽车油箱的容量为c 公升。每公升汽油能行驶e 公里。出发点每公升汽油的价格为p 元。从城市A到城市B 沿途有n 个加油站。第i 个加油站距出发点的距离为di，油价为每公升pi元。如何规划才能使旅行的费用最省。

编程任务：

对于给定的d0,c,e,p,和n 以及n个加油站的距离和油价di 和pi，编程计算最小的旅行费用。如果无法到达目的地，输出“No Solution”。

Input
每组测试数据的第1 行是d0,c,e,p,和n。接下来的n 行中每行2个数di 和pi。

Output
输出最小的旅行费用，精确到小数点后2 位。每个答案1行。

Sample Input
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
Sample Output
26.95

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std ;
double f[10005][2];
double ff[10005][2];
bool run()
{
	double d,c,e,p;
	int n,k;
	if ( ! ( cin>>d>>c>>e>>p>>n ) ) return false;
	int i,j;
	ff[0][0]=0;
	ff[0][1]=p;
	for ( i=1; i<=n; i++ )
	{
		cin>>ff[i][0]>>ff[i][1];
	}
	ff[n+1][0]=d;
	ff[n+1][1]=0;
	n++;
	fill ( &f[0][0],&f[10003][1],0 );
	double t,x;
	double y,a[2],b,q;
	for ( i=1; i<=n; i++ )
	{
		for ( j=0; j<i; j++ )
		{
			t=ff[i][0]-ff[j][0];
			x=f[j][0]*e;
			if ( x>=t )
			{
				y= ( double ) t/e;
				a[0]=f[j][0]-y;
				a[1]=f[j][1];
				q=f[j][0];
			}
			else
			{
				y= ( double ) ( ( t-x ) /e );
				if ( y+f[j][0]>c ) continue;
				a[0]=0;
				a[1]=f[j][1]+y*ff[j][1];
				q=f[j][0]+y;
			}
			if ( ff[j][1]<ff[i][1] )
			{
				b= ( d-ff[j][0] ) /e;
				if ( ( c-q ) <b ) b=c-q;
				for ( k=i+1; k<=n; k++ )
				{
					if ( ( ff[i][0]+b*e ) >=ff[k][0] )
					{
						if ( ff[k][1]<ff[j][1] )
						{
							b= ( ff[k][0]-ff[i][0] ) /e;
							break;
						}
					}
					else
						break;
				}
				a[1]+=b*ff[j][1];
				a[0]+=b;
			}
			if ( a[0]==f[i][0]||f[i][1]==0 )
			{
				if ( a[1]<f[i][1]||f[i][1]==0 )
				{
					f[i][0]=a[0];
					f[i][1]=a[1];
				}
			}
			else if ( a[0]>f[i][0] )
			{
				if ( a[1]< ( a[0]-f[i][0] ) *ff[i][1]+f[i][1] )
				{
					f[i][0]=a[0];
					f[i][1]=a[1];
				}
			}
			else if ( a[0]<f[i][0] )
			{
				if ( a[1]+ ( f[1][0]-a[0] ) *ff[i][1]<f[i][1] )
				{
					f[i][0]=a[0];
					f[i][1]=a[1];
				}
			}
		}
	}

	if ( f[n][1]==0 )
	{
		cout<<"No Solution\n";
	}
	else
		printf ( "%.2lf\n",f[n][1] );
	return true;
}
int main()
{

	while ( run() );
	return 0;
}