UVA1052 Bit Compressor 题解

首先设 $|s|$ 表示字符串 $s$ 的长度，因为原串 $d$ 的长度为 $l$，$1$ 的个数为 $n$，那么 $0$ 的个数即为 $l - n$，因为压缩之后 $0$ 的个数只会变多或者不变，不可能变少，因此 $l - n \le |s|$，否则无解。

接下来想怎么动态规划，设 $dp_{i,t_0,t_1}$ 表示把从 $1$ 往后的位置还原到原串，即原串可以压缩为 $s[i,|s|)$，包含 $t_0$ 个 $0$ 和 $t_1$ 个 $1$ 的方案数，那么最后的答案即为 $dp_{0,l-n,n}$，我们只要知道答案与 $0$ 和 $1$ 的大小关系即可，即判断可行性即可，不需要知道具体答案。考虑如何转移

分类讨论。如果 $s_i$ 为 $0$，那么原串一定为 $0$，答案为 $dp_{i+1,t_0-1,t_1}$；如果 $s_i$ 为 $1$，那么可能与后面的数字构成一个整体，但最后一个位置的下一个一定要为 $0$，否则构成的原串不合法，答案为 $\sum_{p = 2}^i dp_{i + p,t_0,t_1 - x}$。

空间可以优化，我们发现只要存四个数字即可，$0$ 表示无解，$1$ 表示一个解，$2$ 表示多个解，$3$ 表示还未计算，那么我们只需要两个二进制位就能表示值，那么一个整形可以存储十六个值，空间为原来的 $\frac{1}{16}$。还有一种方法，用一个映射来存储值，因为有很多位置是冗余的，没必要全部用上，因此只要存必要的即可。两种方法均可。