DP选做（持续更新ing）

• DP选做（持续更新ing）
  • CF1476F Lanterns

感觉自己DP推式子的能力完全不足，整理一下。

其实也不知道这些极其困难的思维题我到底做不做得来，希望做多了思维的强度也会提升吧。

CF1476F Lanterns

有 \(n\) 个灯笼拍成一排，第 \(i\) 个灯笼具有 \(p_i\) 的亮度。每个灯笼要么朝向左，照亮左边编号为 \([i - p_i,i - 1]\) 的灯笼，要么朝向右，照亮右边编号为 \([i + 1, i + p_i]\) 的灯笼。

寻找一种方案，为所有的灯笼确定朝向，使得每一个灯笼被至少一个其他灯笼照亮。

先想想DP什么吧，我们设计\(dp_i\)表示考虑到\(i\)，能覆盖到的最大前缀是多少，之所以这么设计是因为不会留下空，后续不需要补。

然后我们想一下转移，其实这个时候策略还蛮明显的，就是如果左边没有填满显然就必须填左边，否则填右边是最好的。

然后就分析一下方程怎么写/yun

首先如果\(dp_{i-1}>i\)了，就直接扩展\(dp_i=max(i+p_i,dp_{i-1})\)

否则，根本接不到\(i\)，就直接继承上一个状态\(dp_i=dp_{i-1}\)

然后我们考虑往左扩展是怎么样的，那其实就是覆盖了\([i-p_i,i-1]\)，然后我们要在覆盖了\([1,i-p_i]\)的基础上尽可能地往右扩展，这样的话其实改变了原来已经确定了的点的扩展方向，那我们就枚举来解决这个问题，即在满足\(dp_j\geq i-p_i-1\)的情况下，最大化\(max(i-1,max_{j\leq k\leq i}j+p_j)\)，然后肯定是往右改的越多答案可能会越优，那自然就是让\(j\)尽量的小，这个用\(lowerbound\)实现就好了。