P1016 [NOIP1999 提高组] 旅行家的预算

网址如下：

P1016 [NOIP1999 提高组] 旅行家的预算 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

考前练练手

一道 普及+/提高 难度的题

秒了

想到以前高中的时候被普及难度的题按在地上摩擦，现在能秒洛谷普及+难度的题，有点泪目

代码如下：

#include<stdio.h>
#include<math.h>
typedef struct Station{
    double D;
    double P;
}Station;
void dg(int n, double cost, double c);
const double EPS = 1e-6;
Station S[7];
double minn = 100000000.0, D2, C;
int N;

int main(void)
{
    {
        double D1;
        scanf("%lf%lf%lf%lf%d", &D1, &C, &D2, &S[0].P, &N);
        for(int i = 1; i <= N; i++)
            scanf("%lf%lf", &S[i].D, &S[i].P);
        S[N + 1].D = D1;
    }
    dg(0, 0.0, 0.0);
    if(fabs(minn - 100000000.0) <= EPS)  printf("No Solution");
    else printf("%.2f", minn);

    return 0;
}
void dg(int n, double cost, double c)
{
    if(cost - minn > EPS) return;
    if(n == N + 1){minn = cost;  return;}

    for(int i = n + 1; i <= N + 1; i++)
    {
        double tmp_D = S[i].D - S[n].D;//到下一个地点的距离
        double tmp_C = tmp_D / D2;//到下一个地点所需要的油量
        if(tmp_D - C * D2 > EPS)  break;
        dg(i, cost + (C - c) * S[n].P, C - tmp_C);//加满油的策略
        if(c - tmp_C > EPS || fabs(c - tmp_C) <= EPS)
            dg(i, cost, c - tmp_C);//加到刚好到下一个地点的策略
        else
            dg(i, cost + (tmp_C - c) * S[n].P, 0.0);
    }
    return;
}