题目描述

小疆研发了一款特殊的芯片，在一次处理中，它可以对输入的二进制进行如下的处理:将二进制中的所有“$01$“同时替换为“$10$”。现在给你一个二进制字符串$s$，请你计算若要将该字符串处理为没有"$01$"存在的字符串，这个芯片需要处理多少次。

观察样例，处理步骤为 $\verb!0110101!$$\to$$\verb!1011010!$$\to$$\verb!1101100!$$\to$$\verb!1110100!$$\to$$\verb!1111000!$，易得最终答案一定为 $\verb!111...000!$。

考虑动态规划，状态定义 $dp_i$ 表示第 $i$ 个 $1$ 复位需要的操作次数，不难发现每个 $1$ 左移的过程中会与其左面的 $0$ 进行一次交换操作，所以 $dp_i$ 可以通过 $dp_{i-1}$ 转移，也可以看作与前面所有 $0$ 分别进行交换操作，即通过 $\max(dp_{i-1}+1, pos_i-(i-1))$ 转移，其中 $pos_i$ 表示第 $i$ 个 $1$ 的位置。字符串开头连续的 $1$ 需要特殊处理，最后对所有 $dp_i$ 取 $\max$ 即可。

cpp