题解 P1180 【驾车旅游】

· · 题解

P1180

原本以为是一道朴素的深搜+模拟，然鹅……

算法：深搜+模拟+题意纠正

本题除读题和理解题意之外难度极低……

（题意正确的话这道题该是红/橙题）

Before AC

做题之前先纠正一下题意：

  1. 在每一个停下的加油站总是将油箱加满（不是第一个）
  2. 输出时将答案保留十分位。（不必四舍五入）

好了，理解清楚了题意，这道题瞬间变红题。

还有几个需要注意的点：

  1. 输入是实数的，有可能是浮点数。
  2. 深搜剪枝更加保险。(n ≤ 50)
  3. 司机恰饭还要20元。
  4. “不少于最大容量的一半”，即为大于等于，而不是大于。
  5. 记得加上出发时加油的钱！
  6. 可以把起点、终点作为一个加油站，简化问题。

别抄题解o：

// By Sublime Text 3
// P1180, by Okimoto
// No copy, pls.
#include <stdio.h>
#include <math.h>
using namespace std;
struct stn
{
    double loc;
    double prc;
};
stn gas[64];
int dis, n;
double vol, per, cst, ans;
bool flg = true;
void dfs(double ful, int loc, double sum){
    if(loc == n + 1){
        if(flg){
            ans = sum;
            flg = false;
        }
        else if(sum < ans){
            ans = sum;
        }
        return;
    }
    if((gas[loc + 1].loc - gas[loc].loc) / per > ful){
        sum += 20;
        sum += gas[loc].prc * (vol - ful);
        ful = vol;
        ful -= (gas[loc + 1].loc - gas[loc].loc) / per;
        dfs(ful, loc + 1, sum);
    }
    else if(ful < vol / 2){
        dfs(ful - (gas[loc + 1].loc - gas[loc].loc) / per, loc + 1, sum);
        sum += 20;
        sum += gas[loc].prc * (vol - ful);
        ful = vol;
        ful -= (gas[loc + 1].loc - gas[loc].loc) / per;
        dfs(ful, loc + 1, sum);
    }
    else{
        ful -= (gas[loc + 1].loc - gas[loc].loc) / per;
        dfs(ful, loc + 1, sum);
    }
}
int main(int argc, char const *argv[])
{
    scanf("%d", &dis);
    scanf("%lf %lf %lf %d", &vol, &per, &cst, &n);
    for(int i = 1; i <= n; i ++)
        scanf("%lf %lf", &gas[i].loc, &gas[i].prc);
    gas[n + 1].loc = dis;
    gas[0].loc = 0;
    dfs(vol, 0, 0);
    printf("%.1lf", ans + cst);
    return 0;
}
// 你能看到我，是我最大的心愿♥