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
由于要换车,小明选择公交车直达
|