Spiderman

继续DP。

这题看了数据规模后，一直陷在惯性思维里面：总以为复杂度应该是O(N^2)，结果怎么想也推不出DP公式。

主要是因为这里每个建筑对应的落点有两个值：x坐标和跳数，这两个值之间并无优劣关系，无法简易去重。考虑使用类似边表的方式将每个建筑的所有落点全部存下，再状态转移，发现内存和复杂度都太大。

然后无奈之下写了个SPFA，状态点是xc[1000001]，保存的是到某x坐标时的最小跳数。这种复杂度是O(5000*10^6)，略微超了。

最后看了discuss才明白每个建筑对应的起跳点是有范围的，可以算出来的。由此可以将复杂度降到O(5000*sqrt(10^6))，便能过了。

回顾了一下自己没有想出解法的原因，都是太过于沉浸在惯性思维中，无法跳出来从其他角度构建思路。这种毛病一直都有。究其原因，大概是总无法确定先前的思路是否真的无解，从而放不下，每次思路有所进展后又绕回来重新回到死路上，从而让思考的深度和效率都大打折扣。如果能够把握思路，将不可能的不确定性全部排除，也许就能高效地找到正确求解方向了。

我想如果要做到这些，也没有其他办法的，只有多练多想了。

继续努力。