本文主要是介绍洛谷: P9749 [CSP-J 2023] 公路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路:
贪心思想指的是在对问题求解的时候，总是能做出在当前看来是最好的选择,也就是说，如果要得到整个问题的最优答案，那么要求每一步都能做出最好的选择（feihua）。
在这道题里面，我们希望在来到第i站的时候，使用的是前面i-1站当中油价最低的油。
dp[i] 表示前i站的最低油价（在站点2的时候莫得选，只能用站点1加的油）。然后遍历每个站点，计算来到每个站加多少油，花费多少钱。
#include <bits/stdc++.h>
using namespace std;
#define maxn 100003
#define ll long long
int n, d;//d每升油可以前进的距离
ll v[maxn], a[maxn],dp[maxn];
int main() {cin >> n >> d;for (int i = 1; i <= (n-1); i++) cin >> v[i];for (int i = 1; i <= n; i++) cin >> a[i];dp[1] = a[1];for (int i = 2; i <= n; i++) dp[i] = min(dp[i - 1], a[i]);//经过的价格最便宜的加油站ll s = 0,spend = 0;//需要行驶的距离 花费的钱for (int i = 1; i <= (n-1); i++) {s += v[i];if (s > 0) {spend += ceil(s * 1.0 / d) * dp[i];//需要花多少钱}s -= ceil(s*1.0 / d) * d;//将买的油用完，能够行驶的距离}cout << spend << endl;return 0;
}这篇关于洛谷: P9749 [CSP-J 2023] 公路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
