2336 - 旅行家的预算
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，…，N）。
Input
每个测试文件只包含一组测试数据，每组输入数据的第一行输入D1、C、D2、P、N，其中D1、C、D2、P均为浮点数，N为整数。
接下来N行，每行输入两个浮点数表示离出发点的距离Di和每升汽油的价格Pi。
Output
对于每组输入数据，输出最小费用，结果四舍五入至小数点后两位。如果无法到达目的地，则输出"No Solution"（引号不输出）。
Examples
Input
275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2
Output
26.95
Solution C
#include <stdio.h> #define N 1024 int main() { int i,j,k,n; double d1,c,d2,p[N][2]={0},f,min; scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&p[0][1],&n); n++; for (i=1;i<n;i++) scanf("%lf%lf",&p[i][0],&p[i][1]); p[n++][0]=d1; f=c*d2; for(i=0;i<n;i++) { if (p[i+1][0]-p[i][0]>f) { printf("No Solution"); return 0; } } k =0; min=0; for (i=0;i<n-1;i++) { double d=p[i+1][0]-p[i][0]; while(d) { while(p[i+1][0]-p[k][0]-d>= f) k++; for(j=k;j<= i;j++) if (p[j][1]<p[k][1]) k=j; double max=f-(p[i+1][0]-p[k][0]-d); if(max>d)max=d; d-=max; min+=max/d2*p[k][1]; } } printf("%.2lf\n",min); return 0; }
Solution C++
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #define INF 10000000 #define N 1000010 using namespace std; double ci[N],pi[N]; double dp[N]; int main() { double l,c,m,s; int n; while(cin>>l>>c>>m>>pi[0]>>n) { for(int i=1;i<=n;i++) { scanf("%lf%lf",&ci[i],&pi[i]); } ci[0]=0,ci[n+1]=l,pi[n+1]=INF; s=c*m; for(int i=0;i<=n+1;i++) dp[i]=INF; dp[0]=0; int flag=0; for(int i=0;i<=n;i++) { for(int j=i+1;j<=n+1;j++) { if(s>=ci[j]-ci[i]) { dp[j]=min(dp[j],dp[i]+pi[i]*(ci[j]-ci[i])/m); } else { if(s>=ci[j]-ci[j-1]) dp[j]=min(dp[j],dp[i]+(pi[i]*s+pi[j-1]*(ci[j]-ci[i]-s))/m); else { flag=1; break; } } } if(flag==1) break; } if(dp[n+1]==INF) cout<<"No Solution"<<endl; else printf("%.2lf\n",dp[n+1]); } return 0; }