NOI 2022 Day 1 B. 移除石子
Statement
有一个长为 $n$ 的自然数序列 $a$，我们称其是好的当且仅当可能在进行若干次以下两种操作后变为全 $0$ 序列：
- 选择连续一段数，全部减 $1$，要求长度不小于 $3$。
- 选择一个数，使其减少不少于 $2$。
我们称其是 $k\text{-good}$ 的当且仅当可以给一些数增加并且总共增加 $k$ 后成为好的。
给定 $n,k,\{l_i\},\{r_i\}$，求所有长为 $n$ 且满足 $\forall i\in [1,n],\,l_i\leq a_i\leq r_i$ 的 $a$ 有多少个是 $k\text{-good}$ 的。
$t$ 组多测。
$1\leq t\leq 10,\;1\leq n\leq 10^3,\;0\leq k\leq 100$
Solution
考虑事实上操作间可交换，于是要求先 $1$ 后 $2$，也就是目标是通过若干次 $1$ 操作使得序列中每一项要么是 $0$ 要么不小于 $2$。
先做 $k=0$。
手玩下可以发现一定能使得操作的每一段长度均不超过 $5$，否则可以拆分，以及一个区间不会被操作超过两次，不然可以根本不操作它让最后这个区间上每一项都不小于 $2$。而且一个点不会被覆盖太多次，因为一定可以只在其中某个点变成 $0$ 的时候才操作一个区间，然后一个点变成 $0$ 就不能再被覆盖，因此也会限制周围点的选择，随便分析下可以分析到不超过 $4$，因此你也可以把 $a_i$ 对 $6$ 取 $\min$，再瞪一下发现改成 $5$ 也对。还有一个不知道有没有用的东西是有的操作序列如果使得每一位都和另一个操作序列相同或者多减了至少 $2$ 的话，它一定不优于对方。
那这个题看起来就是 DFA 题，干脆就写一发暴搜状态吧，发现才 $179$ 个状态，再跑个暴力最小化就 $18$ 了，瞪一下转移发现可以让 $a_i$ 对 $4$ 取 $\min$ 了。
那你继续去做 $k$ 更大的情况，首先发现增加 $k$ 几乎可以改成增加不超过 $k$，如果增加不超过 $k-2$ 合法的话 $k$ 也一定合法，只需要再记录下最少加多少石子合法以及这个石子数增加 $1$ 是否还合法即可，这样也就 $202$ 种状态。但是这个其实可以优化，你再瞪一下发现 $k\geq 2$ 时 $k-1$ 合法则 $k$ 合法，而 $k=1$ 时需要特判全 $0$ 以及 $n=3$ 且全 $1$ 的情况，所以我们干脆只记最少花多少即可。
然后这里还是可以找出状态的偏序关系，如果一个方案目前增加的更少且本身方案也偏序了的话就可以把另一个删掉，这样直接搜就能跑出来才 $5722$ 个状态，本地暴力跑下自动机最小化就才 $1721$ 个状态，转移边 $1721\times 5$ 条，直接打表打下来交上去就通过了。