题解：P13008 【MX-X13-T3】「KDOI-12」只有失去光明，才能逃脱黑暗。

yezicong1104 · 2025-06-30 22:05:43 · 题解

题目描述

给定一个非负整数 x，你要经过若干次以下操作将其变成 y，求最小代价：

选择一个 0 \le i \le k，花费 a_i 代价将 x 加或减 2^i。

且操作时不需要保证 x 为非负整数。

算法思路

首先，令 d=\left|x-y \right|，很显然，从 x 变成 y 的过程相当于从 0 变成 d 的过程。

加或减 2^i 代表什么意思？可以将转化为二进制来解决。设一个二进制数的最右边一位是第 0 位，右边第二位是第 1 位，以此类推。所以加或减 2^i 就代表一个二进制数的第 i 位加或减 1。

题目说可以花费 a_i 代价将一个二进制数的第 i 位加或减 1，但将第 i 位加或减 1 的最小代价是 a_i 吗？显然不是。可以设 mina_i 为将第 i 位加或减 1 的最小代价，进行递推。以下是递推公式：

mina_i=\begin{cases} a_i & i = 0 \\ \min(a_i,mina_{i-1} \times 2) & 1 \le i \le k \\ mina_{i-1} \times 2 & i > k \end{cases}

这个公式是怎么来的？

第 0 位只能花费 a_i 来加或减 1。
对于 1 \ge i \ge k，可以花费 a_i，也可以花费两个 mina_{i-1}，两种中选小的那一个。
对于 i>k，只能花费两个 mina_{i-1} 得到。

这是求 mina_i 的代码：

mina[0] = a[0];
for (int i = 1; i <= k; i++)
    mina[i] = min(mina[i - 1] * 2, a[i]);
for (int i = k + 1; i <= 33; i++)
    mina[i] = mina[i - 1] * 2;

接下来有一个简单的思路，我们从低到高来枚举 d 的第 i 位，如果这位是 0，那就跳过；如果是 1，那就将答案加上 mina_i。然而这个方法看似正确，但却存在问题，可以看样例中的第二个数据：

d=(11)_2,mina_0=2,mina_1=4,mina_2=2

最小代价位 4，方法为先花费 2 个代价在第 0 位减 1，这时数从 0 变为 -1。再花费 2 个代价把它的第 2 位加 1，让它变成 (11)_2，一共花费 4 个代价。

这个错误是因为每一位可以加 1 或减 1，且不用保证这个数在操作过程中是非负整数。

所以要改变思路，用 dp 来解决。我们要考虑是否向前进位。设 f(i+1,j) 为解决 d 的 0 到 i 位，向 i+1 为进位为 j 的最小代价。其中 j=0 代表不进位，j=1 代表进位。

枚举 d 的第 i 位和进位 j。设 d 的这一位是 u

若 u+j 是偶数，则不用管，因为这一位加或减 2k，相当于下一位加或减 k。令 f(i+1,(u+j)/2)=\min(f(i+1,(u+j)/2),f(i,j))。
若 u+j 是奇数，这一位既可以加 1 也可以减 1，同上面一种情况，加或减更多也不用考虑。所以令 f(i+1,0)=\min(f(i+1,0),f(i,j)+mina_i)，f(i+1,1)=\min(f(i+1,1),f(i,j)+mina_i)。

dp 的代码：

int d = abs(x - y), cnt = 0;
for (int i = d; i; i /= 2, cnt++);
for (int i = 0; i <= cnt; i++) {
    int u = d >> i & 1;
    f[i + 1][0] = f[i + 1][1] = INF;
    for (int j = 0; j <= min(1, i); j++) {
        if (u + j & 1) {
            f[i + 1][0] = min(f[i + 1][0], f[i][j] + mina[i]);
            f[i + 1][1] = min(f[i + 1][1], f[i][j] + mina[i]);
        } else f[i + 1][u + j >> 1] = min(f[i + 1][u + j >> 1], f[i][j]);
    }
}

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 40;
const LL INF = 1e18;

LL a[N], mina[N], f[N][2];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int x, y, k;
        scanf("%d%d%d", &x, &y, &k);
        for (int i = 0; i <= k; i++)
            scanf("%lld", &a[i]);
        // 求mina
        mina[0] = a[0];
        for (int i = 1; i <= k; i++)
            mina[i] = min(mina[i - 1] * 2, a[i]);
        for (int i = k + 1; i <= 35; i++)
            mina[i] = mina[i - 1] * 2;
        // dp
        int d = abs(x - y), cnt = 0;
        for (int i = d; i; i /= 2, cnt++);
        for (int i = 0; i <= cnt; i++) {
            int u = d >> i & 1;
            //初始化f
            f[i + 1][0] = f[i + 1][1] = INF;
            for (int j = 0; j <= min(1, i); j++) {
                if (u + j & 1) {
                    f[i + 1][0] = min(f[i + 1][0], f[i][j] + mina[i]);
                    f[i + 1][1] = min(f[i + 1][1], f[i][j] + mina[i]);
                } else f[i + 1][u + j >> 1] = min(f[i + 1][u + j >> 1], f[i][j]);
            }
        }
        // 输出
        printf("%lld\n", f[cnt + 1][0]);
    }
    return 0;
}

如果你觉得题解有帮助，请留一个小小的赞，谢谢！