首页 > 迁徙过程中的河流
开通博客写题解
头像 东溪看水
发表于 2020-06-13 14:04:59
解题思路 有 N 个人需要渡河，有一条船，船上最多只能乘坐两人。第 i 个人一个人划船到对面需要 T[i-1] 时间。为了保证船的平衡，当船上有两人时，需按照慢的那个人的速度划船，也就是说船到达对岸的时间等于船上渡河时间长的那个人的时间。求所有人过河的花费时间最少为多少？ 首先将 N 个人按照渡河时 展开全文
去ta的博客 赞 (10) 回复(1) 收起
头像 在刷题的单身狗很开心
发表于 2023-10-15 22:14:04
从题目中规律可以看出来在某个人要过河的时候要么是最快的那个人来接她，要么是还剩下两个让最快的把船开回来然后让这两个过去，之后让第二快的把船开过来，全部过去。这两个在题目中的样例里面都有体现。 dp[i] = max(dp[i-1]+a[0]+a[i], dp[i-2]+a[0]+a[i]+a[ 展开全文
去ta的博客 赞 (2) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”