这是一个创建于 1779 天前的主题，其中的信息可能已经有所发展或是发生改变。
请教下 共享电动车， 小明和小华住同一街上 相隔 X 米。 从小明到小华的路上 有 n 辆电动车 分别在 p1, p2, ...pn 点上。
每一电动车的电量 不同导致每辆车可走的米数不同，d1, d2, ... dn. (从 P* 点开始算） 小明可以确保的是 每两辆相隔的车，都有充足的电量从上一辆到达下一辆 ， 小华可以确保最靠近小华家的那辆车 有足够的电 量到他家从那点出发.
每辆车都有不同的启动金 C1, C2, ...Cn 和每米的价钱 m1, m2, m3...mn. (就是如果小明 启动 电动车 2 ,骑了 4 米 那么小明就是消费了 C2+ 4 * m2 。
当然每当小明遇到一辆电动车， 小明都选择换骑。
小明家里有一辆电动车了， 小明为他冲电的，所以没有启动费， 它可以让小明骑到 P0 米 以每米 m0 的价格
身为刚毕业的小明 如何最低成本从他家开始出发到小华家 同时必须使用电动车作为工具呢？
每一电动车的电量 不同导致每辆车可走的米数不同，d1, d2, ... dn. (从 P* 点开始算） 小明可以确保的是 每两辆相隔的车，都有充足的电量从上一辆到达下一辆 ， 小华可以确保最靠近小华家的那辆车 有足够的电 量到他家从那点出发.
每辆车都有不同的启动金 C1, C2, ...Cn 和每米的价钱 m1, m2, m3...mn. (就是如果小明 启动 电动车 2 ,骑了 4 米 那么小明就是消费了 C2+ 4 * m2 。
当然每当小明遇到一辆电动车， 小明都选择换骑。
小明家里有一辆电动车了， 小明为他冲电的，所以没有启动费， 它可以让小明骑到 P0 米 以每米 m0 的价格
身为刚毕业的小明 如何最低成本从他家开始出发到小华家 同时必须使用电动车作为工具呢？
 | 1 yzbythesea 2020-12-02 07:25:11 +08:00 这图是个 DAG ？这不是拓扑排序吗？ |
 | 2 Herobs 2020-12-02 07:27:32 +08:00 via iPhone 动态规划，状态是每一辆选择骑或者不骑。 |
 | 3 sextoybie OP @yzbythesea 是的，DAG. 该如何跑呢？ |
| 4 sextoybie OP 当然每当小明遇到一辆电动车， 小明都选择换骑。 改为 当然每当小明遇到一辆电动车， 小明都可以选择换骑。 |
 | 6 dartabe 2020-12-02 07:46:19 +08:00 好简单的动态规划 如果我没理解错 当前价格 = 到达前一点的最低价格 + min(所有可用的车从前一点到当前一点的价格) |
| 7 dartabe 2020-12-02 07:51:41 +08:00 我错了 好像不对 |
| 8 dartabe 2020-12-02 07:53:34 +08:00 可能是 dfs 直接算 |
| 11 dartabe 2020-12-02 08:02:58 +08:00 类似于 leetcode 全排列 截止条件不一样 当然我就 leetcode 100 题水平 高手来看下 |
| 13 yzbythesea 2020-12-02 08:08:30 +08:00 |
| 14 yzbythesea 2020-12-02 08:09:19 +08:00 好奇下这是哪家的面试题，难度有点爆炸。 |
 | 15 youngzy 2020-12-02 08:24:42 +08:00 via Android 记录到每个节点时的最小花费，用到当前节点的花费更新后续可到达节点的最小花费。最终结果即为最终节点记录的最小花费。 |
| 16 sextoybie OP @youngzy 嗯 也是这样想的， 就是需要先跑 DP 算出到每个节点时的最小花费。 然后当图是 DAG， 在跑一次？ |
 | 17 xuanbg 2020-12-02 08:31:53 +08:00 小明能够确保的是每两辆相隔的车，都有充足的电量从上一辆到达下一辆 ，所以必须选择换骑啊。最低成本有得选吗？无非就是自己家里的车尽量骑远一点呗。 |
 | 19 futou 2020-12-02 08:41:41 +08:00 如果我没理解错的话，题目指的是车可以从 p1 骑到 p2 或 p3，以此类推。p0 貌似一定要骑到 p1，不过无论怎样不影响解题。 如果是这样的话，这种结构太简单了都用不上 DAG... if 终点是奇数 遍历计算两个相邻奇数点之间的最短路径 求和 else 1. 同奇数处理，然后奇数最短路径+最后一段距离 2. 判断相邻偶数点两两最短路径+p1 到 p2 距离 比较 1. 2.取最短 |
 | 20 ilunny 2020-12-02 08:41:45 +08:00 via Android 感觉有点像路由寻址 |
| 21 xuanbg 2020-12-02 08:42:42 +08:00 这题目命题不够明确，没说小明到小华家不是一条路。。。真是令人头秃 每个相邻点都相同，只是代价不同。这不就是求最短路径吗？ A*算法就是最简单的实现了。 |
| 23 futou 2020-12-02 08:44:25 +08:00 #19 回复完看到了#18 补充信息 2333，参照#15 吧 |
| 24 xuanbg 2020-12-02 08:46:12 +08:00 @xuanbg 这题目命题不够明确，没说小明到小华家不是一条路。。。真是令人头秃 每个相邻点都相通，只是代价不同。这不就是变相的求最短路径吗？两点间的代价就是启动费+里程费，这个代价等同距离。A*算法就是最简单的实现了。 |
 | 25 misdake 2020-12-02 09:44:14 +08:00 骑到 i 点下车的最小代价 cost[i] = min { cost[j] + 骑 j 车到 i 点的代价 }，j 从电量骑到 i 点的车里选，把每个点选择的 j 存下来最后反查 |
 | 26 hejw19970413 2020-12-02 09:45:20 +08:00 贪心就可以 |
| 27 youngzy 2020-12-02 09:47:32 +08:00 @sextoybie 可以在 dp 的时候同时记录转移到该节点的节点编号（也就是当前的最优解是从哪个节点转移过来的），这样在 dp 结束的时候你就有了一个反向的路径链，有需要的话可以进一步处理 |
 | 28 zifangsky 2020-12-02 10:01:32 +08:00 先假设从 P(m) 到其后的某一个点 P(n) 都可以连通，画出一个有向无环图，然后根据「不同导致每辆车可走的米数不同」中的 d1 d2 ... dn 把不可行的边去掉，最后就变成求 最短路问题 了（其中每个边的边长由 C1 C2 ... Cn 和 m1 m2 ... mn 确定） |
 | 29 yazoox 2020-12-02 10:08:20 +08:00 这个题目有难度，有意思。学习一下。 看看有没有大神帖代码出来。 |
| 30 dartabe 2020-12-02 10:23:55 +08:00 我又想了下 dp 可以做 不过要维护一个 dp 数组就可以了 j = 车辆数目 dp 数据长度 j 从尾到头遍历所有车: dp[当前地点] = min(当前车能到达的所有点 + dp[当前车能到达的所有点]) |
 | 31 jsun 2020-12-02 10:56:50 +08:00 动态规划，先维护一个二维数组表示能到达该点电动车，例如能骑到 P6 的是 P3 和 P5，则 A[6]=[3,5]。然后列 dp 公式，dp[6]=Min((P6-P5)*m5+C5+dp[5],(P6-P3)*m3+C3+dp[3]) 。dp[n]=遍历 A[n],求最小值 min |
 | 32 newtype0092 2020-12-02 11:17:28 +08:00 有 test case 么？有点思路但是还需要调试一下，上面几位的解法也不太好验证。 |
 | 34 shunconf 2020-12-02 20:22:50 +08:00 由于要换车，小明选择公交车直达 |
Select Language