p9749专题

洛谷: P9749 [CSP-J 2023] 公路

思路: 贪心思想指的是在对问题求解的时候,总是能做出在当前看来是最好的选择,也就是说,如果要得到整个问题的最优答案,那么要求每一步都能做出最好的选择(feihua)。 在这道题里面,我们希望在来到第i站的时候,使用的是前面i-1站当中油价最低的油。 dp[i] 表示前i站的最低油价(在站点2的时候莫得选,只能用站点1加的油)。然后遍历每个站点,计算来到每个站加多少油,花费多少钱。 #i