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

下面中$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转移，向右喷）就已经决策到了