CSP-T2 75分求助
  • 板块题目总版
  • 楼主Eric12
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/10/27 22:45
  • 上次更新2023/11/2 11:09:24
查看原帖
CSP-T2 75分求助
481471
Eric12楼主2023/10/27 22:45

动态规划做的,不知怎么不得满分,调试好久,并且样例都过了,希望得到帮助。

下面是我的解题思路:

如果前 ii 个站点中油价最低的站点的油价为 minpriceiminprice_i,第 i−1i-1 个站点到第 ii 个站点的距离为 viv_i,从第一个站点到第 ii 个站点最少需要花的钱为 fif_i:

则第 i−1i-1 个站点到第 ii 个站点需要买的最少油量为:

buyyou=ceil⁡(vi÷d)buyyou = \operatorname{ceil}(v_i \div d)

状态转移方程为:

fi=fi−1+buyyou×minpricei−1f_i = f_{i-1}+buyyou \times minprice_{i-1}

这时应该写代码了,但还有一些我们未处理的现象,那就是多买现象。你可能会疑惑在计算第 i−1i-1 个站点到第 ii 个站点需要买的最少油量时为什么使用 ceilceil 向上取整?因为题目中并没有说必须买整数升的油,但是根据样例,我们只能买整数升的油,所以第 i−1i-1 个站点到第 ii 个站点需要买的最少油量必须为整数,也就必须多买一些油凑整。多买的油可行驶路程为:

duobuylc=buyyou×d−viduobuylc= buyyou \times d - v_i

把后面的路程减去多买的路程,多买现象就处理完了,代码如下:

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分,跪求大佬查找错误,谢谢!

2023/10/27 22:45
加载中...