和之前的状态设计中。对应的这则转移比较。
后面一题:
贪心显然是不对的。考虑乱搞:
官方题解:
首先对横线和竖线的坐标分别做镜像翻转,使它们的坐标分别都是单调递增的,
并且相邻的横线和相邻的竖线的距离根原始坐标的距离保持一致。这可以在线性时间内完成,
并且不影响答案。然后按照顺序扫描所有直线,维护从原点出发的两条移动路径。
一条移动路径尽可能往左走,一条移动路径尽可能往右走,
但都保持最短路并且满足规定的直线到达顺序。这两条移动路径分别是上凸曲线和下凸曲线,
每扫描到反向不同的两条直线时就根据交叉点更新其中一条移动路径。
扫描到最后一条直线时就可以算出最短的移动路径长度了。