algorithm - Google CodeJam "Crossing the Road"令人困惑的测试用例

Question

我对这个 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”的路径是什么？

Answer 1

输入可以转化为以下十字路口的时序，其中 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。从那里开始倒推很容易。