CSP-S 2021 第一轮 第36题：完善程序（第 19 题）第 3 空

题目

(1) （魔法数字） 小 H 的魔法数字是 $4$。给定 $n$， 他希望用若干个 $4$ 进行若干次加法、减法和整除运算得到 $n$。但由于小 H 计算能力有限，计算过程中只能出现不超过 $M = 10000$ 的正整数。求至少可能用到多少个 $4$。

例如，当 $n=2$ 时，有 $2=\dfrac{4 + 4}{4}$，用到了 $3$ 个 $4$，是最优方案。

试补全程序。

#include <iostream>
#include <cstdlib>
#include <climits>

using namespace std;

const int M = 10000;
bool Vis[M + 1];
int F[M + 1];

void update(int &x, int y) {
    if (y < x)
        x = y;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i <= M; i++)
        F[i] = INT_MAX;
    ①;
    int r = 0;
    while (②) {
        r++;
        int x = 0;
        for (int i = 1; i <= M; i++)
            if (③)
                x = i;
        Vis[x] = 1;
        for (int i = 1; i <= M; i++)
            if (④) {
                int t = F[i] + F[x];
                if (i + x <= M)
                    update(F[i + x], t);
                if (i != x)
                    update(F[abs(i - x)], t);
                if (i % x == 0)
                    update(F[i / x], t);
                if (x % i == 0)
                    update(F[x / i], t);
            }
    }
    cout << F[n] << endl;
    return 0;
}

③处应填（ ）

选项

• A. F[i] == r
• B. !Vis[i] && F[i] == r
• C. F[i] < F[x]
• D. !Vis[i] && F[i] < F[x]

答案

D

题解

选 D：!Vis[i] && F[i] < F[x]。

这里：

• F[i] 表示目前找到的、凑出数字 i 所需的最少 4 的个数。
• Vis[i] 表示数字 i 的最优答案是否已经确定。

每轮都要从尚未确定答案的数字中，选出 F 值最小的数字 x，再用它与其他数字做运算，更新答案。这与 Dijkstra 算法选取最小距离点的思路相同。

因此，③需要同时满足： ``cpp !Vis[i] // i 尚未确定答案 F[i] < F[x] // i 比当前候选 x 更优 ``

循环开始时 x = 0，而 F[0] = INT_MAX，相当于先把候选值设为无穷大，便于找到最小值。

A、B 把 F[i] 与轮数 r 比较，但轮数并不等于所需的 4 的个数；C 则可能重复选中已经处理过的数字。