蓝桥杯算法训练VIP-旅行家的预算 （C++代码）

解题思路:





注意事项:





参考代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
double d[600]={0},p[600];
double s,c,D,p1;
int n;
double money=0,oil=0;
double locin(int goal,int now)
{
    if(now==n+1)
    {
        printf("%.2lf",money);
        return 0;
    }
    if(now<goal)
    {
        oil-=(d[now+1]-d[now])/D;
        locin(goal,now+1);
        return 0;
    }
    if(now==goal)
    {
        int k=now+1;
        while(p[k]>p[now])k++;
        if(d[k]-d[now]<=D*c)
        {
            if(oil<(d[k]-d[now])/D)
            {
            money+=((d[k]-d[now])/D-oil)*p[now];
            oil=(d[k]-d[now])/D;
            }
            locin(k,now);
            return 0;
        }
        else
        {
            int w=now+1;
            while(d[w]-d[now]<=D*c)w++;
            w--;
            money+=(c-oil)*p[now];
            oil=c;
            locin(w,now);
            return 0;
        }
    }
}
int main()
{
    cin>>s>>c>>D>>p1>>n;
    p[0]=p1;
    for(int i=1;i<=n;++i)
    {
    cin>>d[i]>>p[i];
    if(d[i]-d[i-1]>D*c)    
    {
        cout<<"No Solution";
        return 0;
    }
    }
    d[n+1]=s;p[n+1]=0;
    if(d[n+1]-d[n]>D*c)    
    {
        cout<<"No Solution";
        return 0;
    }
    locin(0,0);
    return 0;
}