CF279E Beautiful Decomposition 题解 动态规划

quanjun · 2022-06-21 00:55:56 · 题解

题目链接：http://codeforces.com/problemset/problem/279/E

题目大意

给定一个 n 位二进制数，你需要将其表示成若干个二的幂（2^k(k \ge 0)）相加或相减的结果。

问：最少需要几个二的幂？

解题思路

首先不难观察每个二的幂最多使用一次（因为对于某个 2^k，如果加两次或者减两次等价于加或减一次 2^{k+1}，加一次并减一次相当于没操作）。

然后我们来看二进制数的最高位，假设最高位对应的是 2^k。因为 2^0 + 2^1 + \ldots 2^{k-1} \lt 2^k，所以要想拥有 2^k，我们必须选择加上某个 2^x，其中 x \ge k。
可以发现加上 2^{k+2} 是不可能的，因为这样我们必须减去一个 2^{k+1} —— 而 2^{k+2} - 2^{k+1} 可以用 2^{k+1} 代替。\Rightarrow 所以此时只能选择 2^k 或者 2^{k+1}。

• 如果我们选择加上 2^k，则我们面临的是是剩余的那些位；
• 如果我们选择加上 2^{k+1}，则我们面临的是 m = 2^{k+1} - n（其中 n 是当前的数值，因为加上了 2^{k+1}，所以剩余的 m = 2^{k+1} - n 就是应该减去的了，因为因为仅仅变换了一下正负号，m 对应的次数是不会有变化的）—— 这里我们将 m 称作 n 的补码（注意：k 的值是不需要定义的，因为 k 就是 n 的二进制表示中的最高位）

然后我们来看状态 m，我们需要翻转 n 的所有二进制位（1 变成 0；同时 0 变成 1），并且结果的次数加 1（因为选择加上了 2^{k+1}）。可以发现一个很神奇的事情（这里是我觉得很神奇的地方，虽然说出来好像有点像废话，但是这句话最重要，能够优化很多问题，很神奇，那就是）：对于原始的 n 来说，若它的补码是 m，则 n 的任意长度的后缀和 m 的同样长度的后缀之间也是补码关系。（所以一开始把 m 求出来即可）

所以在我们正式的处理过程中我们只需要处理 n，m 以及他俩对应的所有后缀。据此得到一个dp解法：

定义 v[1] = n, v[2] = m，则状态 dp[ind][suf] 表示构造 v[ind]（其中 1 \le ind \le 2）的从下标 suf 开始的数所需的最少操作次数。我们可以从 dp[\ldots][n] 开始计算，得到答案为 dp[1][1]。

具体实现时状态略有调整（我的下标从小到大来的）

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;

char s[maxn];
int n, dp[2][maxn];

int main() {
    scanf("%s", s+1);
    n = strlen(s+1);
    dp[0][1] = (s[1] == '1');
    dp[1][1] = 1;   // 一开始 2^{k+1} 边反码至少要一次
    for (int i = 2; i <= n; i++) {
        if (s[i] == '0') {
            dp[0][i] = dp[0][i-1];
            dp[1][i] = min(dp[1][i-1], dp[0][i-1]) + 1;
        }
        else {  // s[i] == '1'
            dp[1][i] = dp[1][i-1];
            dp[0][i] = min(dp[1][i-1], dp[0][i-1]) + 1;
        }
    }
    printf("%d\n", dp[0][n]);
    return 0;
}