题解：P2836 加油问题

Cartis · 2024-10-11 10:40:07 · 题解

题目传送门

看到数据范围这么小，直接考虑搜索。

思路

使用搜索加上剪枝，使用选与不选搜索，判断是否在这个点加油。

注意点

油箱内的油的余量大于等于一半时，不能主动停下来，所以我们在大于等于一半时就不能选择加油，但是如果小于一半，那么我们就可以加油也可以不加油，但是如果走不到下一个点，这个时候就必须加油。

并且一开始的时候油箱也需要加油。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 1;
double k, c, d, l;
int n;
double a[N], oil[N], minn = 1e18;
void dfs(int cur,double il, double cnt){
    if (cnt > minn) return ; // 最优性剪枝。
    if (cur > n){
        minn = min(minn, cnt);
        return ;
    }
    if (il * d >= a[cur + 1] - a[cur]){ // 如果能走到下一个点。
        if (il >= c / 2.0){ // 不能加油
            dfs (cur + 1, il - (a[cur + 1] - a[cur]) / d, cnt);
        }else { // 可以加也可以不加
            dfs (cur + 1, il - (a[cur + 1] - a[cur]) / d, cnt);
            dfs (cur + 1, c - (a[cur + 1] - a[cur]) / d, cnt + 2 + (c - il) * oil[cur]);
        }
    }else{ // 必须加油，走不到下一个点
        dfs (cur + 1, c - (a[cur + 1] - a[cur]) / d, cnt + 2 + (c - il) * oil[cur]);
    }
}
signed main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> k >> c >> d >> l >> n;
    for (int i = 1;i <= n;i ++){
        cin >> a[i] >> oil[i];
        oil[i] /= 100; // 注意分要变成元需要除以100
    }
    a[n + 1] = k;
    dfs (1, c - a[1] * 1.0 /d, l); // 搜索
    printf ("%.2lf", minn); // 注意保留两位小数
    return 0;
}