题解 | 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]即可获得最终耗费