题解：CF2283E Partition of a Binary String

· · 题解

本篇题解无需组合数基础，所有方案数均是 DP 递推求法。

第一问：最大代价

显然，一个位置对最终答案的贡献是 1 或者 2。我们尝试刻画最优情况是什么样的。

对于一个位置 i，尽量让它产生 2 的贡献。会发现当且仅当它与不同的数相邻时才可以。考虑这样的选择长什么样：要么像 01 一样长度为 2，要么像 010 这样长度为 3，不可能更多——形如 0101 这样的会不满足题目的合法性限制。

第一问的答案呼之欲出：01 交替的序列每一个位置贡献 2，其余的贡献 1。

第二问：方案数

现在就可以拎出来若干段极长的 01 交替序列，对它们分别 DP 求方案数。

设 f[i] 表示以 i 为结尾的方案数。由于每块长度只可能是 2 或者 3，转移也是平凡的：

f[i]=f[i-2]+f[i-3]

初始值为 f[0]=1,\ f[1]=0,\ f[2]=1。

并且，我们会发现这些段互不影响；进一步的，对于一串连续的 0 或 1 产生的贡献，也不会被影响到。所以利用乘法原理，最终答案的一部分就是把各个部分的方案数乘起来。

对于剩下的 01 分开统计。以 0 举例：0 可以随便放入若干个集合。设 g[i][j] 表示考虑了 i 个 0，放入了 j 个集合的方案数，转移：

g[i][j] \leftarrow g[i-1][j-1] g[i][j] \leftarrow g[i-1][j]\cdot j

其中第一式表示新开一个集合，第二式表示沿用原来的集合。

总方案数是

\sum_{i} g[x][i],

其中 x 是除去 01 交替序列后 0 的个数。

最终答案

最终方案数就是三部分的乘积（乘法原理）：

\left(\prod_{\text{各交替段}} f[\text{段长}]\right) \times \left(\sum_{i} g[x_0][i]\right) \times \left(\sum_{i} g[x_1][i]\right),

其中 x_0,x_1 分别是除去 01 交替序列后剩余的 0 和 1 的个数。