UVA1052 Bit Compressor 题解

_Jocularly_ · 2025-11-21 11:25:40 · 题解

首先设 |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}。还有一种方法，用一个映射来存储值，因为有很多位置是冗余的，没必要全部用上，因此只要存必要的即可。两种方法均可。