本菜不会写，看了别人的博客才恍然大悟，细节很多，具体再注释中可以体现。
友情链接：
https://blog.csdn.net/zhao2018/article/details/83420944
//F
#include<stdio.h>
#include<string.h>
#define MAXN 60
#define INF 0x3f3f3f3f
double dp[MAXN];//dp[i]从第i个加油站到终点的最小费用(循环体是逆序)不包括在i点加油的费用,而且在i点必须加油
double dis[MAXN];//每个加油站到起点的距离
double price[MAXN];//加油站的油价
int record[MAXN];//记录加油站的序号
int Link[MAXN][MAXN];
int main()
{
int i,j;
int cnt;
double alllen;//起点到终点的总距离
double oilbox,km_oil,cost;//油箱容量,每升油的最大行驶公里数，起点加油的初始费用,加油站的数量
int num;
double temp;
int u;
scanf("%lf",&alllen);
scanf("%lf%lf%lf%d",&oilbox,&km_oil,&cost,&num);
for(i=1;i<=num;i++)
scanf("%lf%lf",&dis[i],&price[i]);
i=num;
while((alllen-dis[i])/km_oil<=oilbox)
dp[i--]=0;
dis[num+1]=alllen;
dis[0]=0;
//cnt=0;
memset(Link,0,sizeof(Link));
for(;i>=0;i--)//0是起点,此处一定要遍历到0，否则1号加油站永远都算到dp[1]是不包含此处加油的费用的，所以如果1号加油站加了油，则费用要当i=0时才会被计算到
{
dp[i]=INF;
for(j=i+1;j<=num;j++)//必须是正序因为下面的continue意思是在j点不需要加油，但是在这点之后一定至少有一点要加油，因为否则就会被上面的while循环筛掉
{
if((dis[j]-dis[i])/km_oil>oilbox)//连j点都到达不了
continue;
if((dis[j]-dis[i])/km_oil<oilbox/2&&(dis[j+1]-dis[i])/km_oil<=oilbox)//在j点油箱过半且可以到达下一站
continue;
temp=(dis[j]-dis[i])/km_oil*price[j];//j点要加油了
temp+=2;
temp+=dp[j];
if(temp<dp[i])
{
dp[i]=temp;
u=j;
}
}
Link[i][u]=1;
//record[++cnt]=u;
}
cnt=0;
for(i=0;i<num;)
{
for(j=i+1;j<=num;j++)
{
if(Link[i][j]==1)
{
i=j;
record[++cnt]=j;
break;
}
}
if(i!=j)//没有一个需要加油的，则直接跳出
break;
}
printf("%.2lf %d\n",dp[0]+cost,cnt);
for(i=1;i<=cnt;i++)
printf("%d ",record[i]);
printf("\n");
return 0;
}
