代码一:

#include <bits/stdc++.h>
using namespace std;
#define db double
#define INF (1e8 - 1)
db d1,c,d2,p,ans,res,t,k,maxx;
int n;
struct node {
    db dis,co;
    bool friend operator<(const node &a, const node &b)
    {
        return a.dis<b.dis;
    }
}l[600];
int LYC(int now)
{
    int flag = INF;db dd = l[now].dis;
    for(int i = now + 1; i <= n && l[i].dis - dd <= maxx ; i++)
    {
        if(l[i].co < l[now].co) 
        {
            ans += ((l[i].dis - res - dd)/d2) * l[now].co;//桎梏的就是"前缀"和"多余"
            return i;//接下来从i递归 
        }
        if(flag == INF || l[i].co < l[flag].co) flag = i;//追踪相对较小的,这个标记无论什么情况下都合理 
    }
    if(d1 - dd <= maxx)//即便有剩余的距离,但如果满油到不了,那没了 
    {
        ans += ((d1 - dd - res)/d2)*l[now].co;
        return INF;
    } 
    if(flag == INF) {cout << "No Solution" << endl;return -1;}
    else 
    {
        ans += c*l[now].co;res = maxx - (l[flag].dis - dd);//求的是"相对"的距离
        return flag;
    }
}
int main()
{
    cin >> d1 >> c >> d2 >> p >> n;
    l[0].dis = 0,l[0].co = p;
    for(int i = 1 ; i <= n ; i++) cin >> l[i].dis >> l[i].co;
    maxx = c*d2;
    sort(l,l+1+n);
    do{
        t = LYC(k),k = t;
        if(t == -1) return 0;
    }while(t != INF);
    printf("%.2lf",ans);
    return 0;
}

代码二:

#include <bits/stdc++.h>
using namespace std;
#define re register
#define db double
db d[600],p[600],nd[600];
int n,f;
db d1,c,d2,ans = 1e8 - 1,maxx;
void dfs(int idx,db oil,db mo)
{
    if(idx == n+1)
    {
        if(mo < ans) ans = mo;
        f = 1;
        return;
    }
    if(maxx < nd[idx]) return;
    db dd = 0;
    for(int i = idx; i <= n ; i++)
    {
        dd += nd[i];
        if(maxx < dd) break;//吆西 
        dfs(i+1,c-dd/d2,mo+(c-oil)*p[idx]);
        dfs(i+1,0,mo+max((db)0,(dd/d2-oil)*p[idx]));
    }
}
int main()
{
    cin >> d1 >> c >> d2 >> p[0] >> n;
    for(re int i = 1 ; i <=  n; i++){
        cin >> d[i] >> p[i];
        nd[i-1] = d[i] - d[i-1];//从这点到后面那点的距离 
    }
    nd[n] = d1 - d[n];
    maxx = c*d2;
    dfs(0,0,0);
    if(f) printf("%.2lf",ans);//所有ans中找最小的 
    else puts("No Solution");
    return 0;
}