动态规划做的,不知怎么不得满分,调试好久,并且样例都过了,希望得到帮助。
则第 i−1 个站点到第 i 个站点需要买的最少油量为:
buyyou=ceil(vi÷d)
状态转移方程为:
fi=fi−1+buyyou×minpricei−1
这时应该写代码了,但还有一些我们未处理的现象,那就是多买现象。你可能会疑惑在计算第 i−1 个站点到第 i 个站点需要买的最少油量时为什么使用 ceil 向上取整?因为题目中并没有说必须买整数升的油,但是根据样例,我们只能买整数升的油,所以第 i−1 个站点到第 i 个站点需要买的最少油量必须为整数,也就必须多买一些油凑整。多买的油可行驶路程为:
duobuylc=buyyou×d−vi
把后面的路程减去多买的路程,多买现象就处理完了,代码如下:
int j;
for(j=i+1;j<=n&&v[j]<duobuylc;j++)
{
duobuylc-=v[j];
v[j]=0;
}
if(j<=n)v[j]-=duobuylc;
这思路彻底有了,写代码:
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
int n,d,p[100001],f[100001],minprice[100001];
double v[100001];
int main()
{
// freopen("road.in","r",stdin);
// freopen("road.out","w",stdout);
memset(minprice,0x3f,sizeof(minprice));
scanf("%d%d",&n,&d);
v[1]=0;
for(int i=2;i<=n;i++)
scanf("%lf",&v[i]);
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
minprice[i]=min(minprice[i-1],p[i]);//钱i个站点的最便宜油价
}
f[1]=0;
for(int i=2;i<=n;i++)
{
int buyyou=ceil(v[i]/double(d)),duobuylc=buyyou*d-v[i];
//buyyou:买的油数量,duobuylc:多买的油可行驶路程
f[i]=f[i-1]+buyyou*minprice[i-1];
//状态转移方程
int j;
for(j=i+1;j<=n&&v[j]<duobuylc;j++)
{
duobuylc-=v[j];
v[j]=0;
}
if(j<=n)v[j]-=duobuylc;
//把后面的路程减去多买油可以行驶的路程
}
printf("%d",f[n]);
return 0;
}
但是不知为啥,只有75分,跪求大佬查找错误,谢谢!