记忆化搜索 首先来看这个题 第一问很好做，直接 dfsdfsdfs 或 bfsbfsbfs 求一下最下面一排的店有没有不能被覆盖到的就行了 关键是第二问 首先很明显的思路，对第一排每个点进行 dfsdfsdfs 或 bfsbfsbfs ，搜出每个点能够覆盖到的区间，再做线段覆盖就行了 时间复杂度理论最差是 OOO ( nnn * mmm ^ 2+n2+n2+n ^ 222 )会 ttt 一个点，卡常好的话应该是能过掉的 但这题真的要这么高的复杂度嘛？ 我们首先可以证明：如果有解，我们每个点覆盖的城市(线段)一定是连续的 因为如果不是连续，我么们可以很容易的证明这个点无法到达（它所在联通块边界一定高于相邻点） 所以，我们只要求出每个点能到达最左和最右的点就行了，而这个点肯定是不变的 所以我们能够想到什么？ dpdpdp 对于每个点（ iii ， jjj ） lll [ iii ][ jjj ] =min=min=min ( lll [ kkk ][ lll ]) 点（ kkk ， lll ）是（ iii ， jjj ）能到的的所有点 但我们发现，这个图并不是严格从下向上或者从上向下的 是可以向上走的（样例 111 就很好的说明了这点） 所以我们直接 dpdpdp 是不可以的 那我们就用到了记忆化搜索 对于已经求出的（ kkk ， lll ），直接调取所求数据，否则 bfsbfsbfs / dfsdfsdfs 去查找 这样就避免了直接 dfsdfsdfs 进行的对同一点的反复调用 甚至可以把记忆化和第一问结合起来，直接一边 dfsdfsdfs 求出 最后再进行线段覆盖就行了