柒葉灬 的博客

柒葉灬 的博客

牛客网NOIP赛前集训营-提高组(第四场)-灭虫

posted on 2019-10-17 15:47:39 | under 未分类 |

下面中 $l_i,r_i$ 表示的是能喷到的下标位置,不再是输入的长度

dp状态定义

$dp[i][j]$ 表示前 $i$ 个喷头已经确定了方向(当然喷头需要先按 $p_i$ 排序),最远喷到了 $j$ 这个位置(当然所有 $p_i , r_i , l_i $ 已经离散化过了)

dp转移

一个喷头,你可以让他往左边喷,也可以让他往右边喷,也可以不喷。 不喷的情况就是说他喷的区间其他喷头喷的区间覆盖了。

如果当前点是 $i$ ,且最远喷到的点是 $j$

  1. 向左喷,相当于覆盖 $[l_i,p_i]$ ,贡献就是实际能覆盖的区间长度(实际能覆盖的意思是有 $l_i<j$ 的情况,即当前区间和上一个区间重合了)

  2. 向右喷,相当于覆盖 $[p_i,r_i]$ ,也是较复杂的情况,因为这么覆盖之后可能会影响后面的喷头,所以为了防止出错直接把后面的喷头也一起决策了。

    设 $[p_i,r_i]$ 覆盖了下标为 $[i,nxt]$ 的喷头,对于这个区间的喷头,贪心的决策,从中选一个喷左边能喷最远的 $L_i$ 一个喷右边最远 $R_i$ 的,将答案转移到 $dp[nxt][R_i]$ 就行了。

    (如果这喷最左边的和喷最右边的是同一个喷头应该知道怎么做吧,就不说了)

  3. 不喷,至于为什么会有不喷的情况。。。因为喷头如果喷,那就要增加限制(后面的喷头不能喷前面的了),下面个图表示一下,(0表示没覆盖的点,1表示覆盖的点)

    0010011000 ,而此时出现了一个能覆盖全部的喷头,就会被转移成

    0010011111 ,而这不是我们想要的。

    如果假设前面的喷头就不喷好了,那就就会有一个状态是

    0000000000,而这个状态就可以被转移成

    1111111111。得到了希望得到的状态

覆盖的情况

Q1:很多人应该想的和我一开始想的一样,怎么记录前面几个点没有被喷到?比如说我先来个 $[1,3]$ 再来个 $[4,6]$ ,只记录喷的最右端点,万一后面还有个 $[0,10]$ 怎么办。

A1:因为转移的时候喷头是可以不喷的,所以这种情况在前两个喷头不喷的情况下可以转移到。

Q2:那如果一个左边的喷头 $i$ 喷右边,而右边的喷头 $j$ 又喷左边了怎么办?

A1:如果 $j$ 喷头能完全覆盖 $i$ 喷头,那么在 $i$ 喷头不决策的情况下能转移到。如果 $j$ 喷头能喷到 $i$ 左边, $i$ 能喷到 $j$ 的右边,在之前贪心的时候(见上文dp转移,向右喷)就已经决策到了