题意

最少用多少钱从 $1$ 到 $n$

PS：上次没用完的油可以留到这次用

思路

能少用点钱就少用点

当当前的油价比后面几个点都便宜，就在这个点备好，直到到更便宜的点的油价再加

用 $dis$ 记录当前能走的路程，要加油时就减掉再加油

代码^[1]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005,INF = 0x7fffffff;
int a[N] = {INF},v[N],dis,sum;
signed main(int argc, char **argv){
	int n,d;
	cin >> n >> d;
	for (int i = 1;i < n;i++){
		cin >> v[i];
	}
	for (int i = 1;i <= n;i++){
		cin >> a[i];
		if (a[i - 1] < a[i])	a[i] = a[i - 1];	// 有更便宜的油价
	}
	for (int i = 1;i < n;i++){
		int addo = ceil(1.0 * (v[i] - dis) / d);	// 要加多少油[^1]
		dis += addo * d;	// 能走的路程
		sum += addo * a[i];	// 花了多少钱
		dis -= v[i];	// 减掉到下一个点的路程
	}
	cout << sum;
	return 0;
}

稻版题解

题意

最少用多少钱从 1 到 n

PS：上次没用完的油可以留到这次用

思路

能少用点钱就少用点

当当前的油价比后面几个点都便宜，就在这个点备好，直到到更便宜的点的油价再加

用 dis 记录当前能走的路程，要加油时就减掉再加油

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005,INF = 0x7fffffff;
int a[N] = {INF},v[N],dis,sum;
signed main(){
	int n,d;
	cin >> n >> d;
	for (int i = 1;i < n;i++){
		cin >> v[i];
	}
	for (int i = 1;i <= n;i++){
		cin >> a[i];
		if (a[i - 1] < a[i])	a[i] = a[i - 1];	// 有更便宜的油价
	}
	for (int i = 1;i < n;i++){
		int addo = ceil(1.0 * (v[i] - dis) / d);	// 要加多少油
		dis += addo * d;	// 能走的路程
		sum += addo * a[i];	// 花了多少钱
		dis -= v[i];	// 减掉到下一个点的路程
	}
	cout << sum;
	return 0;
}