题解 | To Fill or Not to Fill

#include <bits/stdc++.h>
using namespace std;

double dp[30005];

struct station {
    double price;
    int dis;
};

bool cmp(station a, station b) {
    return a.dis < b.dis;
}
int main() {
    int Cmax, D, Davg, N;
    while (cin >> Cmax >> D >> Davg >> N) { // 注意 while 处理多个 case
        for (int i = 0; i <= D; i++) dp[i] = INT_MAX;
        int maxlen = Cmax * Davg;

        vector<station> v;
        while (N--) {
            station tmp;
            cin >> tmp.price >> tmp.dis;
            v.push_back(tmp);
        }
        sort(v.begin(), v.end(), cmp);
        for (int i = 0; i < v.size(); i++) {
            int start = v[i].dis;
            double price = v[i].price;
            for (int j = 1; j <= maxlen; j++) {
                dp[start + j] = min(dp[start + j], price);
            }
        }
        double price = 0;
        int flg = 1;
        for (int i = 1; i <= D; i++) {
            if (dp[i] == INT_MAX) 
            {
                flg = 0;
                cout <<"The maximum travel distance = "<<
                fixed<<setprecision(2)<< (i - 1)*1.0 << endl;
                break;
            }
            price+=dp[i];
        }
        if(flg) cout<<fixed<<setprecision(2)<<price/Davg<<endl;

    }
}
// 64 位输出请用 printf("%lld")

很有区间合并的感觉

用dp[i]记录每单位最佳油耗即可，累加[1,D]的dp[i]即可获得最终耗费