刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

猫吃鱼

明明家从1号站点出发,开车去旅游,一共要经过n个站点,依次为 2、3......n。由于明明带上了心爱的小猫,在每个站点都要为小猫提供一条鱼用做美餐(包括1号站点)。除了1号站点只能吃1号站点买的鱼,其他站点既可以吃当地买的鱼,也可吃之前经过的站点买了存入车载冰箱中的鱼。

但车载冰箱消耗的电能来自汽油,所以每条鱼用冰箱保存到下一站的费用与各个站点的汽油价格有关为使问题简化,我们约定:

(1)车从某站开出时油箱中都是此站点刚加的汽油

(2)车载冰箱能容纳一路上需要的所有鱼。

即:每条鱼的费用既包括购买时的费用,也包括用冰箱保存鱼的费用。

编程实现:

为了降低小猫吃鱼的总代价,明明预先上网查到了这n个站点的鱼价和汽油价格。并据此算出每个站点买一条鱼的费用以及从该站点到下一站用冰箱保存一条鱼的费用。你能帮明明算出这一路上小猫吃鱼的最小总费用吗?

输入:

第一行: 站点数n,1<n<100

接下来的n行:每行两个以空格分隔的正整数,表示:这一站买一条鱼的费用,以及从这一站把每条鱼保存到下一站的费用,两个费用均为小于 10000 的正整数

输出:

最小总费用,是一个正整数

样例输入:

5
63
71
32
83
95

样例输出

29

样例数据分析:

第一行数据5代表一共5站

第二行数据63代表本站购买鱼6元,运费3元,第一站必须一定先购买一条 总花费6元

第三行数据71代表本站购买鱼7元,运费1元,从上一站最小花费+运费9元大于本站购买的费用7,所以选择从本站购买鱼总花费 6+7=13元

第四行数据32代表本站购买鱼3元,运费2元,从上一站最小花费+运费8元大于本站购买的费用3,所以选择从本站购买鱼,总花费 6+7+3=16元

第五行数据83代表本站购买鱼8元,运费3元从上一站最小花费+运费5元,小于本站购买的费用8,所以选择从上站花费加上本站运费总花费6+7+3+5=21元

第六行数据95代表本站购买鱼9元 运费5元,从上一站最小花费+运费8元,小于本站购买的费用9,所以选择从上一站花费加上本站运费总花费6+7+3+5+8=29元

最终总花费为29元

使用微信搜索喵呜刷题,轻松应对考试!

答案:

这是一个动态规划的问题。首先,我们创建一个大小为n+1的一维数组dp,dp[i]表示小猫在到达第i个站点时,吃到鱼的最小总费用。然后,我们遍历每个站点,对于每个站点i,我们有两种选择:1. 在当前站点i买鱼,那么费用就是dp[i-1] + cost[i] + fee[i],其中dp[i-1]表示到达上一个站点时吃到鱼的最小总费用,cost[i]表示在当前站点买鱼的费用,fee[i]表示将鱼保存到下一站的费用。2. 在之前的某个站点j(j

解析:

【喵呜刷题小喵解析】:
这个问题是一个典型的动态规划问题,可以使用动态规划的方法来解决。动态规划是一种将问题分解为多个子问题,通过求解子问题的最优解来得到原问题的最优解的方法。在这个问题中,我们可以将问题分解为n个子问题,每个子问题表示小猫到达第i个站点时,吃到鱼的最小总费用。

首先,我们创建一个大小为n+1的一维数组dp,dp[i]表示小猫在到达第i个站点时,吃到鱼的最小总费用。然后,我们遍历每个站点,对于每个站点i,我们有两种选择:在当前站点i买鱼,或者在之前的某个站点j(j
具体实现时,我们可以使用一个循环来遍历每个站点,对于每个站点i,我们再使用一个循环来遍历之前的每个站点j(j
在这个问题中,我们需要注意一个问题,就是每个站点的鱼价和汽油价格不同,因此我们不能直接将买鱼的费用和保存到下一站的费用相加得到总费用。我们需要将买鱼的费用和保存到下一站的费用分别存储在一个数组中,然后在进行选择时,根据这两个数组计算出总费用。

此外,由于这是一个动态规划的问题,我们需要将子问题的解保存下来,以便在求解子问题时使用。我们可以使用一个一维数组dp来保存子问题的解,dp[i]表示小猫在到达第i个站点时,吃到鱼的最小总费用。在求解子问题时,我们可以直接使用这个数组来得到子问题的解,而不需要重新计算。
创作类型:
原创

本文链接:猫吃鱼 明明家从1号站点出发,开车去旅游,一共要经过n个站点,依次为 2、3......n。由于明明

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share