Open Wizmann opened 4 years ago
Problem Code
在一条长度为n的线上有m个点d1, d2...dm，其中d1 == 0, dm == n。
一个人从d1（0点）出发向前奔跑，当他到达另一个点的时候可以变换方向（+1方向或-1方向），在两点之间方向不能变化，也不能跑出[0, n]的范围。一个时间单位里，人可以移动1个单位距离。
又给定一个红绿灯，绿灯持续时间为G，红灯持续时间为R。当绿灯亮起时，一定处于奔跑状态。当红灯亮起时，人必须位于一个点di，然后在di点等待R时间。开始奔跑时，绿灯恰好亮起
问人从d1（0点）奔跑到dm（n点），最小需要多少时间。
注意：只要人奔跑到了dm点，就算完成任务，不需要一定要在红灯亮起的时候”恰好“到达。
简单题和难题的一个重要区别是，简单题的思路相对单一，如果掌握了其背后的性质或不变量就可以直接解题。难题的思路相对多元化，即使你做出了一些可行的尝试，也不一定是可以用来解决问题的那一些。
本题的一些性质：
k * (R + G) + dm - dx
性质1是完全正确的，但是它对于解题并没有什么帮助。虽然我们只枚举奇数，但是枚举每一条路径走过的次数仍然是O(G)的。整体的时间复杂度不符合要求。
再考虑性质2。其实在整个过程中，人的状态可以由一个dp[p][t] = k来表示，意味着在点p时，消耗了k (R + G) + t的时间。这个空间复杂度是O(m G)的。如果我们能保持时间复杂度也为O(m * G)，那么就找到了一个可行的解决方案。
但是问题来了，我们实际上在解决一个最短路问题。而最短路的时间复杂度明显不符合要求。这里引入了一种01-BFS的算法。由于在状态转移中，k的值的变化只能为0或+1。当k值变化为0时，我们可以将其直接放到队列头部，而不会影响最终的结果。（01-BFS请参考这里，随便找了一个解释）
感觉这题其实就是为01-BFS量身定做的，如果之前不知道这个东西，这题大概是没有思路的吧。。。
Problem Code
题意
在一条长度为n的线上有m个点d1, d2...dm，其中d1 == 0, dm == n。
一个人从d1（0点）出发向前奔跑，当他到达另一个点的时候可以变换方向（+1方向或-1方向），在两点之间方向不能变化，也不能跑出[0, n]的范围。一个时间单位里，人可以移动1个单位距离。
又给定一个红绿灯，绿灯持续时间为G，红灯持续时间为R。当绿灯亮起时，一定处于奔跑状态。当红灯亮起时，人必须位于一个点di，然后在di点等待R时间。开始奔跑时，绿灯恰好亮起
问人从d1（0点）奔跑到dm（n点），最小需要多少时间。
注意：只要人奔跑到了dm点，就算完成任务，不需要一定要在红灯亮起的时候”恰好“到达。
解法
本题的一些性质：
k * (R + G) + dm - dx。在dx点出发之前，一定经过k轮的绿灯+红灯性质1是完全正确的，但是它对于解题并没有什么帮助。虽然我们只枚举奇数，但是枚举每一条路径走过的次数仍然是O(G)的。整体的时间复杂度不符合要求。
再考虑性质2。其实在整个过程中，人的状态可以由一个dp[p][t] = k来表示，意味着在点p时，消耗了k (R + G) + t的时间。这个空间复杂度是O(m G)的。如果我们能保持时间复杂度也为O(m * G)，那么就找到了一个可行的解决方案。
但是问题来了，我们实际上在解决一个最短路问题。而最短路的时间复杂度明显不符合要求。这里引入了一种01-BFS的算法。由于在状态转移中，k的值的变化只能为0或+1。当k值变化为0时，我们可以将其直接放到队列头部，而不会影响最终的结果。（01-BFS请参考这里，随便找了一个解释）