先跪谢大佬为敬!
思路是从后往前找最小油价(最小油价站点记为m),m至n站点所需汽油全部在m站点买好,然后在1-m站点间重复此操作,直至m'==1
蒟蒻代码:
#include<iostream>
#include<cmath>
using namespace std;
int n,d;
int v[100005],a[100005];
int cost(int l,int r)
{
if(l==r)
return 0;
int p,minn=0x3f3f3f3f;
for(int i=l;i<=r;i++)
{
if(a[i]<minn)
{
minn=a[i];
p=i;
}
}
long long int afm,cafm;
for(int i=p;i<=r-1;i++)
{
afm+=v[i];
}
cafm=((int)ceil(afm/d))*minn;
return cost(l,p-1)+cafm;
}
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];
}
cout<<cost(1,n)<<endl;
return 0;
}
谢谢巨佬!!!!!