这是一个创建于 1470 天前的主题，其中的信息可能已经有所发展或是发生改变。
请教下 共享电动车， 小明和小华住同一街上 相隔 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