我对这个 CodeJam 问题有疑问:Crossing the Road
我实现了动态规划解决方案,并在“B-small-practice.in”(点击“解决 B-small”获取文件)上比较了运行我的程序和第一名获胜者程序的结果。
我的程序在所有 100 个测试用例中都给出了正确答案(与第一名获胜者的程序相同),只有两个测试用例除外:#5 和 #6。
让我们看看案例 #5:
2 2
1 1 0 10 1 6
10 1 0 1 10 10
有4个路口。我的答案是“17”。正确答案是“12”。我不明白怎么可能得到“12”;当我尝试手动执行时,我能得到的最好结果是“17”。成本为“12”的路径是什么?
最佳答案
输入可以转化为以下十字路口的时序,其中 NS 表示允许行人向北或向南横穿的时间,EW 表示允许行人向东或向西横穿的时间。
A -- NS:0 EW:1 NS:2 EW:3
B -- NS:0-4 EW:5 NS:6-15 EW:16 NS:17-26
C -- NS:0-9 EW:10 NS:11-20
D -- EW:0-9 NS:10 EW:11-20
如果您在时间 16 沿 EW 方向穿过十字路口 B,很容易看出您如何以时间 17 结束。但关键是您永远不必在 EW 方向穿过 B。
从时间 12 开始倒推,解必须在时间 11 沿 NS 方向穿过交点 B。从那里开始倒推很容易。
关于algorithm - Google CodeJam "Crossing the Road"令人困惑的测试用例,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23505898/