-
非常好的容斥 dp 题
-
发现这道题分为没有找到颜色 \(B\) ，找到连续 \(K\) 个颜色 \(B\) 但没找到颜色 \(W\) 以及都找到了三种状态，因此我们考虑把这些状态记为 \(0,1,2\) 设到 dp 中
-
设计状态：设 \(dp_{i,j,k}\) 表示前 \(i\) 个数，状态为 \(j\)，第 \(i\) 个数为 \(k\) 的方案数( \(0B1W\) )
-
转移：首先我们容易想到枚举第 \(i-1\) 个数填什么，即
\[dp_{i,j,k}=dp_{i-1,j,0}+dp_{i-1,j,1} \]但这显然不对，因为这时候可能出现状态之间的跨越，例如在填第 \(0\) 中状态时恰好填了连续 \(k\) 个 \(B\)，从而转移到状态 \(1\)。怎么办？我们考虑使用容斥。
对于 \(dp_{i,0,k}\)，我们先枚举第 \(i-1\) 位填什么，然后考虑使用容斥减掉出现了连续个颜色 \(k\) 的部分，容易发现即为 \(dp_{i-K,0,k\oplus 1}\)。对于其他状态同理，最终得到递推式：
\[\begin{align} dp_{i,j,k}&=dp_{i-1,j,0}+dp_{i-1,j,1}\\ dp_{i,0,k}&-=dp_{i-K,0,k\oplus 1}\\ dp_{i,1,k}&+=dp_{i-K,0,k\oplus 1}\\ dp_{i,1,k}&-=dp_{i-K,1,k\oplus 1}\\ dp_{i,2,k}&+=dp_{i-K,1,k\oplus 1}\\ \end{align} \]其中要注意的是对于第 \(2,3\) 的式子当且仅当 \((i-K,i]\) 中所有数都为 \(B\) 时才满足条件，\(4,5\) 式子同理，可以使用前缀和来判断区间中是否有某个颜色
-
最终答案：\(dp_{n,2,0}+dp_{n,2,1}\)
-
-
最终复杂度 \(O(n)\)
bzoj#2958. 序列染色
发布时间 2023-11-12 20:33:50作者: FOX_konata