不好评价？
首先我们考虑最基础的情况，当 \(k=0,l_i=r_i\) 时，相当于我们需要判定一个状态能不能被消完。
这相当于我们要执行若干次 \(2\) 操作，使得每个位置要么大于等于 \(2\)，要么为 \(0\)。为此我们需要挖掘一些操作 \(2\) 的性质。
性质 \(1\)：操作区间长度不会超过 \(5\)
因为如果大于等于 \(6\) 就一定能拆成更小的区间。
性质 \(2\)：对于每个点，以这个点为结尾的区间个数和以这个点为开头的区间个数都不会超过 \(2\)，并且不会是长度为 \(4\) 与 \(5\) 的区间
假设有三个区间，则一定是 \(3,4,5\)，那么将 \(4,5\) 的左端点用一次二操作，则 \(4,5\) 变成后一个点的 \(3,4\)，这一定更优。
性质 \(3\)：对于每个点，经过这个点的区间个数不会超过 \(3\)
我也不会证明……但是有了前两个结论写个暴力搜一搜应该是容易的吧！
于是我们大概就可以写出一个 dp 了。设 \(dp_{i,j,k}\) 表示到了第 \(i\) 个点，经过第 \(i\) 个点的区间个数为 \(j\)，以第 \(i\) 个点为开头的区间个数为 \(k\)，有没有一种可能。则这个应该满足 \(k\leq j,k\leq 2,j\leq 3\) ，转移应该是平凡的，时间复杂度 \(O(n)\)。
再考虑到 \(k> 0\) 的情况，一种暴力的 dp 就是再加一维，复杂度变成 \(O(nk^2)\)。
虽然能过了，但是我们还是来尝试优化一下。
我们猜想，当 \(a_i\geq b\) 的时候都是等价的，其中 \(b\) 是一个小常数。因为经过一个点的区间个数不超过 \(3\)，而再把这个点消掉需要至少两个，因此 \(b\) 的一个下界是 \(6\)，这已经很优秀了，但是实际上 \(b\) 是可以取到 \(5\) 的，不过差不多（
所以每个点放的个数不超过 \(b\)，复杂度优化到 \(O(nk)\)。
另一个优化的角度是值和状态互换。如果放的石子数满足，当放 \(k\) 个石子可以 win时，放 \(k+1\) 个石子也可以满足，那么我们可以令 \(dp_{i,j,k}\) 为使用石子数的最小值，这样复杂度就是 \(O(n)\) 的。但是这满不满足呢？
当 \(k=0\) 的时候显然是满足的，当 \(k=1\) 的时候有两种情况不满足：全 \(0\)，或者 \(n=3\) 且全 \(1\)。
当 \(k\geq 2\) 的时候，只需要考虑 \(k=1\) 的两种不满足情况。全 \(0\) 显然不会出现，如果 \(n=3\) 且全 \(1\) 我们就可以放成两个 \(2\) 一个 \(0\)。因此对于 \(k\geq 2\) 都是满足的。 \(k=1\) 的情况特判就行。
状态看上去不是很多，之后就是套路 dp 套 dp 了。如果按照第一种方法压状态在 \(k=100\) 的时候大概是 \(5\times 10^4\) 个状态，光把这些东西搜出来就 T 了。按照第二种方法搜大概是 \(1.2\times 10^4\) 个状态，时间复杂度 \(O(TnS(n))\)，卡卡常就能过。
标签：luogu,复杂度,石子,个数,满足,NOI2022,移除,区间,dp From： https://www.cnblogs.com/275307894a/p/17450195.html