观察样例 1 的解释，发现切换类型的方法是比较单一的
这种就是直接走一段换一段，我们可以人为钦定换乘时最多走一步，因为相邻的同色也可以视作走车站
这种情况复杂一些，需要往回走一段，但是依然可以发现往回走也至多一步，因为如果走了两步说明往回走了一步到达的车站依然同色，那么走的车站必然不会是后面那一个
根据这两个性质，发现最短路的形态非常单一，只会从上一个红色或蓝色的车站转移过来，因此设 \(dp_{i,j,k,0/1}\) 表示考虑到第 \(i\) 个车站，上一个红色的车站的最短路为 \(j\)，蓝色的为 \(k\)，上一个车站为红 \(/\) 蓝色，转移时考虑如果上一步放红色车站，且这一步放红色车站，那么红色车站最短路更新为 \(j+1\)，蓝色无法更新，如果放蓝色车站，那么红色车站最短路更新为 \(min(j,k+2)\)，蓝色车站最短路更新为 \(min(j+1,k+1)\)，上一步放红色车站是对称的
这样做的复杂度是 \(O(n^3)\)，发现最短路更新时，仅当 \(|j-k|<2\) 时才可能无法确定最短路的更新，否则与 \(|j-k|=2\) 的情况是等价的，因此复杂度优化到 \(O(n^2)\)
标签：AtCoder,一步,蓝色,车站,短路,Express,ARC119F,更新,红色 From： https://www.cnblogs.com/pidan123/p/17706482.html