python/TangDou/LanQiaoBei/LanQiao14STEMA202212/4.cpp

#include <bits/stdc++.h>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 110;
int n; // 电桩数
int d; // 冲一次电能跑的距离
int res = INF;
int a[N];
/*
测试用例：
5 4
3 1 2 2 1

答案：3

*/
void dfs(int u, int r, int c) {
    if (u == n + 1) {
        res = min(res, c);
        return;
    }
    // 现在剩余的油量是r,加满的话油量是d
    //  如果现在剩余的油量r不足以跑完下一个路a[u+1],那么必须在本站加油到d
    if (d < a[u + 1]) return;

    if (r >= a[u + 1]) { // 我有两种选择：1、在本站不加油，2、我就加满
        dfs(u + 1, r - a[u + 1], c);
        dfs(u + 1, d - a[u + 1], c + 1);
    } else
        dfs(u + 1, d - a[u + 1], c + 1);
}
int main() {
    cin >> n >> d;
    for (int i = 1; i <= n; i++) cin >> a[i];

    dfs(0, 0, 0);

    if (res == INF)
        cout << -1 << endl;
    else
        cout << res << endl;
    return 0;
}