编程实现:（P1809 过河问题）小青要赶 N (2<N<100) 匹小马过河，N 匹小马过河都需

简答题

编程实现:（P1809 过河问题）

小青要赶 N (2<N<100) 匹小马过河，N 匹小马过河都需要一定的时间(分钟)，小青每次过河最多能赶两匹小马 (骑一并赶一匹)，返回时需骑一匹，每次过河的时间为走的慢的小马花费的时间。请计算至少需要多长时间才能把 N 匹小马全部赶过河。

例如: N = 4，4 匹小马过河需要的时间分别为 1，2，3，4 (单位: 分钟)。

用时最少的一种过河方式:

第一次:赶 1 分钟和 2 分钟的小马过河，然后骑 1 分钟的小马返回，共花费 3 分钟 (过去花费 2 分钟，回来花费 1 分钟)

第二次:赶 3 分钟和 4 分钟的小马过河，然后骑 2 分钟的小马返回，共花费 6 分钟 (过去花费 4 分钟，回来花费 2 分钟)

第三次: 赶 1 分钟和 2 分钟的小马过河，共花费 2 分钟 (过去花费 2 分钟)

总共最少花费的时间是 11 分钟（3+6+2=11）

输入说明

两行整数，第一行表示总共有多少匹马 N（2<N<100），第二行表示每匹马过河所需要的时间，数字之间以英文逗号隔开

输出说明

一行一个整数，表示将所有马儿赶过河所需要的最短时间

【输入样例】

4
1,2,3,4

【输出样例】

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

答案：

根据题目要求，我们可以使用动态规划算法来解决这个问题。我们可以定义一个数组dp，其中dp[i]表示小青需要将前i匹小马全部赶过河所需的最短时间。我们可以按照小马过河所需时间从小到大的顺序进行遍历，对于每个小马j，我们需要计算两种情况下的时间，即赶j和j+1过河，然后返回骑j过河的时间加上dp[j+1]。另一种情况是只赶j过河，然后返回骑最快的小马过河的时间加上dp[j-1]。我们取这两种情况中的较小值作为dp[i]的值。最后返回dp[N]即可。

解析：

【喵呜刷题小喵解析】：
这个问题可以使用动态规划算法来解决。首先，我们需要将输入的小马过河所需时间按照从小到大的顺序进行排序。然后，我们可以定义一个数组dp，其中dp[i]表示小青需要将前i匹小马全部赶过河所需的最短时间。我们可以按照小马过河所需时间从小到大的顺序进行遍历，对于每个小马j，我们需要计算两种情况下的时间，即赶j和j+1过河，然后返回骑j过河的时间加上dp[j+1]。另一种情况是只赶j过河，然后返回骑最快的小马过河的时间加上dp[j-1]。我们取这两种情况中的较小值作为dp[i]的值。最后返回dp[N]即可。

这个问题需要注意一些细节。首先，我们需要对输入的小马过河所需时间进行排序，否则会导致计算结果不正确。其次，我们需要在计算dp[i]的值时，需要保证j+1和j-1不会越界。最后，我们需要取两种情况下的较小值作为dp[i]的值，否则会导致计算结果偏大。

在实现代码时，我们可以使用一个循环来遍历小马过河所需时间，然后使用一个嵌套的循环来计算dp[i]的值。在计算dp[i]的值时，我们需要使用if语句来判断j+1和j-1是否越界，然后取两种情况下的较小值作为dp[i]的值。最后返回dp[N]即可。

具体的实现代码如下：

```python
def min_time(n, times):
times.sort() # 按照小马过河所需时间从小到大排序
dp = [0] * (n + 1)
for i in range(2, n + 1):
dp[i] = min(times[i - 1] + dp[i - 1], times[i - 2] + dp[i - 2])
return dp[n]

n = int(input().strip())
times = list(map(int, input().strip().split(',')))
print(min_time(n, times))
```
其中，min_time函数用于计算将所有小马赶过河所需的最短时间，输入参数为小马数量n和小马过河所需时间列表times。函数内部首先对times进行排序，然后定义一个数组dp，其中dp[i]表示小青需要将前i匹小马全部赶过河所需的最短时间。然后使用一个循环来遍历小马过河所需时间，使用一个嵌套的循环来计算dp[i]的值，最后返回dp[n]即可。

创作类型：

原创

本文链接：编程实现:（P1809 过河问题）小青要赶 N (2<N<100) 匹小马过河，N 匹小马过河都需

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

分享考题

答案：

解析：

最热门资讯

JAVA工程师面试指导--猎头内部资料

常见面试问题100问！