(魔法数字）小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;


	___(1)___;


	int r=0;


	while (___(2)___) {


		r++;


		int x=0;


		for (int i = 1; i <= M; i++)


			if (___(3)___)


				x=i;


		Vis[x]=1;


		for (int i = 1; i <= M; i++)


			if (___(4)___) {


				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;


}

选择题