#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
    int num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
        if(x=='-')bj=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9') {
        num=num*10+x-'0';
        x=getchar();
    }
    return num*bj;
}
int n;
double dist,Cap,Mile,Max,Dist[105],Price[105],f[105];
int main() {
    ios::sync_with_stdio(false);
    memset(f,0x7f,sizeof(f));
    cin>>dist>>Cap>>Mile>>f[0]>>n;
    Max=Cap*Mile;
    Dist[n+1]=dist;
    for(int i=1; i<=n; i++) {
        cin>>Dist[i]>>Price[i];
        Price[i]/=Mile; //转为走一英里所需要的钱（元） 
    }
    for(int i=1; i<=n+1; i++)
        for(int j=i-1; j>=0&&Dist[i]-Dist[j]<=Max; j--) {
            if(i==n+1)f[i]=min(f[i],f[j]);
            if(Dist[i]-Dist[j]<=Max/2&&Dist[i+1]-Dist[j]<=Max)continue; //当前虽然小于一半但是可以被后面替代 
            f[i]=min(f[i],f[j]+(Price[i]*(Dist[i]-Dist[j])+20));
        }
    printf("%0.1lf",f[n+1]);
    return 0;
}

/*
OTZ动态规划？
数据范围实在太小了n在50以内
直接dfs搜索就好了
这题目有点坑的地方就在于题意的理解
{
（1）除非汽车无法用油箱里的汽油达到下一个加油站或目的地，在油箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来；
（2）在每个停下的加油站总是将油箱加满；    
}
因为是每次将油箱装满所以问题会简单很多
主要我们来看第一个问题
这句话怎么理解？
很坑啊意思就是，如果汽车无法到达下一站，则一定要加油
如果油箱还有一半少的油，那么可以加油也可以不加油(当然前提是只有能到下一站才可能不加油)
那么如果油箱有一半多的油    并且能到下一站就是不能加油的
有点绕自己好好理解(%%%%各位语文学霸)
然后我们就直接dfs一下就好
事实证明    裸的dfs也可以轻轻松松50ms内解决所有的点
但是为了训练一下特地加了个优化
我们用minw[i]表示第i个加油站之后可能达到的最便宜的油费
然后预处理递推一下就好了
当我们发现不管怎么样剩下的距离需要的油钱+当前消费
都会>目前的最优解时  直接剪枝就好了
这只是个粗略的剪枝   其实肯定还可以更好的
但是就懒得再继续写了
超级水的一道题
唉好好的一道动规被你们玩坏了
城市套路深   城里人真会玩
这个程序可以直接秒杀了QWQ
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=55;
struct node 
{
    double x,w;
}a[MAXN];
double S,v,W,L;
double minw[MAXN];
double ans=999999.0;
int n;

void init()
{
    cin>>S>>L>>v>>W;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].w;
    a[n+1].x=S;
}

void getshort()
{
    minw[n]=a[n].w;
    for(int i=n-1;i>=1;i--)
        minw[i]=min(minw[i+1],a[i].w);
}

inline void dfs(int x,double l,double waste)
{
    if(x==n+1)
    {
        ans=min(ans,waste);
        return;
    }
    if(waste+max(double(0),(a[n+1].x-a[x].x)/v-l)*minw[x]>=ans)
        return;
    if(l<L/2||l*v<a[x+1].x-a[x].x)
        dfs(x+1,L-(a[x+1].x-a[x].x)/v,waste+(L-l)*a[x].w+20);
    if(l*v>=a[x+1].x-a[x].x)
        dfs(x+1,l-(a[x+1].x-a[x].x)/v,waste);
}

int main()
{
    init();
    getshort();
    dfs(1,L-a[1].x/v,W);
    printf("%.1lf\n",ans);
    return 0;
}
     

Block code

#include <algorithm>
#include <iostream>
#include<string.h>
#include <fstream>
#include <math.h>
#include <vector>
#include <cstdio>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define exp 1e-8
#define fi first
#define se second
#define ll long long
#define INF 0x3f3f3f3f
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()
#define mm(a,b) memset(a,b,sizeof(a));
#define for1(a,b) for(int a=1;a<=b;a++)//1---(b)
#define rep(a,b,c) for(int a=b;a<=c;a++)//b---c
#define repp(a,b,c)for(int a=b;a>=c;a--)///
#define stl(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
using namespace std;
void bug(string m="here"){cout<<m<<endl;}
template<typename __ll> inline void READ(ll &m){ll x=0,f=1;char ch=getchar();while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}m=x*f;}
template<typename __ll>inline void read(__ll &m){READ(m);}
template<typename __ll>inline void read(ll &m,ll &a){READ(m);READ(a);}
template<typename __ll>inline void read(ll &m,ll &a,__ll &b){READ(m);READ(a);READ(b);}
template<typename __ll>inline void read(ll &m,ll &a,__ll &b,__ll &c){READ(m);READ(a);READ(b);READ(c);}
template<typename __ll>inline void read(ll &m,ll &a,__ll &b,__ll &c,__ll &d){READ(m);READ(a);READ(b);READ(c);read(d);}
template < class T > T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template < class T > T lcm(T a, T b) { return a / gcd(a, b) * b; }
template < class T > inline void rmin(T &a, const T &b) { if(a > b) a = b; }
template < class T > inline void rmax(T &a, const T &b) { if(a < b) a = b; }
template < class T > T pow(T a, T b) { T r = 1; while(b > 0) { if(b & 1) r = r * a; a = a * a; b /= 2; } return r; }
template < class T > T pow(T a, T b, T mod) { T r = 1; while(b > 0) { if(b & 1) r = r * a % mod; a = a * a % mod; b /= 2; } return r; }

double l,v,u,k;
int n;
double dat[60][2];
double ans;
void dfs(int idx,double pre,double cost) //当前站点，上一个站点剩下的油，开到上一个站点的花费
{
if(pre*u<dat[idx][0]||cost>=ans)return ;
if(idx==n+1)
{
ans=min(ans,cost);
return ;
}
pre-=dat[idx][0]/u; //剩余的油量
if(pre<v/2.0)
{
dfs(idx+1,v,cost+(v-pre)*dat[idx][1]+20);
dfs(idx+1,pre,cost);
}
else if(idx!=n&&pre*u<dat[idx+1][0])
dfs(idx+1,v,cost+(v-pre)*dat[idx][1]+20);
else dfs(idx+1,pre,cost);
}
int main()
{
cin>>l>>v>>u>>k>>n;
for1(i,n)cin>>dat[i][0]>>dat[i][1];
dat[++n][0]=l,dat[n][1]=0;dat[0][0]=0;
for(int i=n;i>=1;i--)
dat[i][0]-=dat[i-1][0];
ans=INF;
dfs(1,v,k);
printf("%.1f\n",ans);
}

var distance,capacity,km:real;
ic,minc:longint;
n:byte;
station:array[0..50,1..2] of real;
procedure init;
var i:byte; c:real;
begin
readln(distance);
readln(capacity,km,c,n);
ic:=round(c*100);
for i:=1 to n do
begin
readln(input,station[i,1],station[i,2]);
station[i,2]:=station[i,2]*100;
end;
end;

procedure search;
procedure drive(stop:byte;cost:longint);
var num:byte;
begin
if station[stop,1]+capacity*km>=distance then
begin
if cost<minc then minc:=cost;
exit;
end;
num:=stop+1;
while (num<n) and (station[num+1,1]<=station[stop,1]+capacity*km) and (station[num,1]<=station[stop,1]+capacity*km/2) do
inc(num);
if(num=n) or (station[num+1,1]>station[stop,1]+capacity*km) then
drive(num,cost+2000+round((station[num,1]-station[stop,1])/km*station[num,2]));
while (num<=n) and (station[num,1]<=station[stop,1]+capacity*km/2) do
inc(num);
while (num<=n) and (station[num,1]<=station[stop,1]+capacity*km) do
begin
drive(num,cost+2000+round((station[num,1]-station[stop,1])/km*station[num,2]));
inc(num);
end;
end;
begin {search}
minc:=maxlongint;
drive(0,ic);
end;

procedure print;
begin
writeln(minc/100:0:1);
end;

begin
init;
search;
print;
end.

#include<cstdio>
#include<iostream>
using namespace std;
double a,c,d,k,m=0xfffffff,s[51][3]={0};
int n;
void f(int t,double o)
{
int u;
if(s[t][1]+a*k>=d)
{
if(o<m)
m=o;
return;
}
u=t+1;
while(u<n&&s[u+1][1]<=s[t][1]+a*k&&s[u][1]<=s[t][1]+a*k/2)
u++;
if(u==n||s[u+1][1]>s[t][1]+a*k)
f(u,o+20+(s[u][1]-s[t][1])/k*s[u][2]);
while(u<=n&&s[u][1]<=s[t][1]+a*k/2)
u++;
while(u<=n&&s[u][1]<=s[t][1]+a*k)
{
f(u,o+20+(s[u][1]-s[t][1])/k*s[u][2]);
u++;
}
}
main()
{
int i;
cin>>d>>a>>k>>c>>n;
for(i=1;i<=n;i++)
cin>>s[i][1]>>s[i][2];

f(0,c);
printf("%.1lf",m);
}

暴力DFS踩标程OTZ

我就是个2b，还想dp预处理出f[i]表示从加油站i加满油到终点的最小代价

好简单的题呵~~

当初浪费了我好几个小时

现在不到半个小时就AC~~

一定要注意！

当剩余油量>=一半油箱容量时，如果不能到达下一站，还是得加油！

每个加油站付的钱四舍五入到0.1元，一定要忽略这句！！！害得我多交了两次。。。

题目描述与数据不符~~

提高一个百分点- -

还是由于粗心WA了一回

一次通过

用DFS就能秒杀哦

为什么这样的题目通过的人这么少呢？

修改下题目:

[问题描述]

如今许多普通百姓家有了私家车,一些人喜爱自己驾车从一个城市到另一个城市旅游.自己驾车旅游时总会碰到加油和吃饭的问题, 在出发前,驾车人总要想方设法得到从一个城市到另一个城市路线上的加油站的列表,列表中包括了所有加油站的位置及其每升的油价(如3.25/L).驾车者一般都有以下的习惯:

(1) 在油箱里还有不少于最大容量一半的汽油时, 除非汽车无法用油箱里的汽油达到下一个加油站或目的地, 驾驶员从不在加油站停下来;

(2) 在油箱里的油少于最大容量一半的汽油时,可停可不停;

(3) 在每个停下的加油站总是将油箱加满;

(4) 在加油站加油的同时,买快餐等吃的东西花去20元.

(5) 从起始城市出发时油箱总是满的.

(6) 加油站付钱总是精确到0.01元(四舍五入).

(7) 驾车者都知道自己的汽车每升汽油能够行驶的里程数.

现在要你帮忙做的就是编写一个程序,计算出驾车从一个城市到另一个城市的旅游在加油和吃饭方面最少的费用.

[输入]

第一行是一个实数,是从出发点地到目的地的距离(单位:km).

第二行是三个实数和一个整数,其中第一个实数是汽车油箱的最大容量(单位:L);第二个实数是汽车每升油能行驶的公里数;第三个实数是汽车在出发地加满油箱时的费用(单位:元);一个整数是1到50间的数,表示从出发地到目的地线路上加油站的数目.

接下来N行都是两个实数,第一个数表示从出发地到某一个加油站的距离(单位:KM);第二个实数表示该加油站汽油的价格(单位:元).

数据项中的每个数据都是正确的,不需判错.一条线路上的加油站根据其到出发地的距离递增排列并且都不会大于从出发地到目的地的距离.

[输出]

就一个数据,是精确到0.1元(四舍五入)的最小的加油和吃饭费用.

[样例]

tour.in

600

40 8.5 128 3

200 3.52

350 3.45

500 3.65

tour.out

379.6

搜索- -||

谁有DP的方法共享下..

除非汽车无法用油箱里的汽油达到下一个加油站或目的地，在油箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来……

我们语文课正在学习判断病句，这个被我发现了。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

DP就可以了

f[i]->max(f[j]+20+消耗的油补上的钱，f[i])

f[i]表示到i个加油站的时候所需要的最低费用，把终点设为最后一个加油站，加油为0元，但是要注意DP条件，即（（当剩下的油少于1/2）或（（即使大于）且（不足以到i+1个加油站））） 且 （油足够到i加油站） 【注意（很重要）】

最后输出就可以了。

每个加油站付的钱四舍五入到0.1元

请无视这句话！！！！！

还是那句话：程序简洁是美德，暴力搜索是王道！大胆地搜吧，数据最大只有50个站大多数站还只有1个选择。即不能到达下一站或者剩油超过一半都只有一个选择，能到达下一站且剩油不足一半可选择继续开或停下加油！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

奇怪？

我算样例应为311.7元？

顺序：1-2-终点。

why？

请大牛指教，小弟不胜感谢！