五、完善程序-1

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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;
}