无

无

AtCoder Beginner Contest 177

见本周推荐

无

无

无

无

AtCoder Beginner Contest 177

无

AtCoder:

I hate Shortest Path Problem

题意:

给出一个$n*m$的方格,每一行有一些格子是禁止向下走的.现在要求从第一行的某个格子出发,每一次只能向下或者向右走,问走到第$i$行最少要走几步.

tag:线段树

题解:

用一棵线段树维护从第一行走到下面某一行的所有位置各需要走几步.考虑如何向下转移.假如说不能向下走的区间是$[l,r]$,那么线段树中的$[1,l-1],[r+1,m]$位置的值+1,$[l,r]$位置的值加正无穷.又因为,$r+1$这个位置可能从左边的某个位置走过来(显然不用考虑更往右的位置),所以还需要建一个线段树维护下$ans_{i}-i$的值,每次用一个最小值来更新$r+1$这个位置.

comment:自己的思路有一个漏洞,没有考虑$r+1$这个位置.

咕咕咕

咕咕咕