简答题 偏难
#23295

(魔法数字)小 H 的魔法数字是 4。给定n,他希望用若干个 4 进行若干次加法、减法和整除运算得到 n。但由于小 H 计算能力有限,计算过程中只能出现不超过M…

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

例如,当 n = 2 时,有 2 = (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;

}

未登录也能判分,登录后才会记录
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。