Pascal(fpc 3.0.2) 解法, 执行用时: 1ms, 内存消耗: 128K, 提交时间: 2018-06-30 08:23:09

var
 n,i,j,minlow,minhigh,k:longint;
 d,p:array[0..110]of real;
 tank,money,c,d1,ps,d2,fd:real;
begin
 readln(d1,c,d2,ps,n);
 tank:=0;money:=0;d[0]:=0;p[0]:=ps;
 d[n+1]:=d1;p[n+1]:=200000;
 for i:=1 to n do readln(d[i],p[i]);
 for i:=1 to n+1 do
  if d[i]-d[i-1]>c*d2 then begin writeln('No Solution');exit;end;
 i:=0;fd:=c*d2;
 repeat
  minlow:=0;minhigh:=0;
  j:=i+1;
  while (d[j]<=d[i]+fd)and(j<=n+1) do
   begin
    if p[j]<p[i] then begin minlow:=j;break;end;
    inc(j);
   end;
  k:=j-1;
  if minlow>0 then
   begin
    money:=money+p[i]*((d[minlow]-d[i])/d2-tank);
    tank:=0;
    i:=minlow;
   end
  else
   begin
    if k=n+1 then
      begin
       money:=money+p[i]*((d[n+1]-d[i])/d2-tank);
       break;
      end;
    minhigh:=i+1;
    for j:=i+2 to k do
     if p[j]<p[minhigh] then minhigh:=j;
    money:=money+p[i]*(c-tank);
    tank:=c-(d[minhigh]-d[i])/d2;
    i:=minhigh;
   end;
 until i=n+1;
 writeln(money:0:2);
end.

C++ 解法, 执行用时: 3ms, 内存消耗: 404K, 提交时间: 2021-07-21 15:13:15

#include<bits/stdc++.h>

using namespace std;
int const MANX=20;
int n,f;
double Ans=0x3f3f3f3f,sum,c,dis;
double d[MANX],p[MANX],nd[MANX];
void dfs(int st,double oil,double mo)
{
	if(st==n+1)
	{
		if(mo<Ans) Ans=mo;
		f=1;
		return;
	}
	if(c*dis<nd[st]) return;
	double nx=0;
	for(int i=st;i<=n;i++)
	{
		nx+=nd[i];
		if(dis*c<nx) break;
		dfs(i+1,c-nx/dis,mo+p[st]*(c-oil));
		dfs(i+1,0,mo+max((double)0,p[st]*nx/dis-p[st]*oil));
	}
	return;
 }
 int main()
 {
 	cin>>sum>>c>>dis>>p[0]>>n;
 	for(int i=1;i<=n;i++)
 	{
 		cin>>d[i]>>p[i];
 		nd[i-1]=d[i]-d[i-1];
	 }
	 nd[n]=sum-d[n];
	 dfs(0,0,0);
	 if(f)
	 {
	 	printf("%.2lf",Ans);
	 }
	 else printf("No Solution");
	 return 0;
 }