特殊点(15分)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long LL;
LL v[N],p[N]; 
int main()
{
	LL n,d;
	cin>>n>>d;
	LL s=0;
	for(int i=1;i<n;i++)
	{
		int x;
		cin>>x;
		s+=x;
	}
	LL a;
	cin>>a;
	LL m=(s+d-1)/d*a;
	cout<<m;
    return 0;
}

55分

• 计算当前站走到当前站需要的油量，从前面找一个最小值

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010;
int n,d;
int v[N],a[N];
int main()
{
	cin>>n>>d;
	for(int i=1;i<n;i++)
	{
		cin>>v[i];
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	LL res=0,oil=0,dist=0;
	for(int i=2;i<=n;i++) //枚举走到哪个站 
	{
		dist+=v[i-1];//更新距离
		LL t=(dist+d-1)/d-oil; //更新从前面过来需要的油量
		int price=1e6;
		for(int j=1;j<i;j++) //找到最便宜的价格
		{
		    price=min(price,a[j]);
		}
		res+=t*price;
		oil+=t;
	}
	cout<<res;
	return 0;
}

100分

• 在第二个的基础上，使用一个变量维护前面的最小值。

#include
using namespace std;
typedef long long LL;
const int N=100010;
int n,d;
int v[N],a[N];
int main()
{
	cin>>n>>d;
	for(int i=1;i<n;i++)
	{
		cin>>v[i];
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	LL res=0,oil=0,dist=0;
	int price=a[1];
	for(int i=2;i<=n;i++) //枚举走到哪个站 
	{
		dist+=v[i-1];//更新距离
		LL t=(dist+d-1)/d-oil; //更新从前面过来需要的油量
		res+=t*price;
		oil+=t;
		price=min(price,a[i]);//更新价格 
	}
	cout<<res;
	return 0;
}