一进制奶牛计数(ONE)
提交文件名：ONE.PAS
问题描述：
众所周知，奶牛们没有手指，因此，很遗憾他们不能使用十进制计数。他们采用的是一种称为“一进制”的计数表示方法。
这种计数方法包含：数字“1”，加号，减号，乘号和一些括号。这样的计数方法可以表示任何正整数。例如，22 = 1+1 + ((1+1+1+1) * (1+1+1+1+1))，用了11个1来表示22，因此，该表达式的UCC长度就是11。
而另一种表示22的计数方法如下：1 + (1+1+1) * (1+(1+1)*(1+1+1))，这个表达式的UCC长度是10（因为用了10个1来表示22）。而且，没有其他UCC长度更短的表达式能表示22了。
奶牛总是懒惰的，因此，他们总是在寻找一种简洁的表达式来表示正整数。请你编写程序，对给定的正整数，告诉奶牛们用“一进制”的表达式来表示该正整数，最短的UCC长度是多少。
输入文件（ONE.IN）：
输入数据有多个，每个只有一行，一个正整数N（1≤N≤2,000,000）。
输出文件（ONE.OUT）：
对应每个输入，输出每行一个整数，为表示N的最短UCC长度是多少。
输入输出样例：
ONE.IN
22
10
ONE.OUT
10
7
几种很明显。直接看程序。
View Code 1 program one1; 2 var i,j,k,n,m:longint; 3 f:array[0..2000000] of longint; 4 5 function min(a,b:longint):longint; 6 begin 7 if am then m:=n; 32 end; 33 34 close(input); close(output); 35 End.
=======
LZC用数学推得。
留下看看吧。
View Code 1 //f[i]记录i的最小ucc长度用于记忆化 2 //对于任意的n=a*b+c或者n=a*b-c 3 //则f[n]=min(f[a]+f[b]+f[c]); 4 //n=a*p^r+c（p为素数）当r足够大，f[n]=f[a]+f[p]*r+f[c] 5 //因此2000000只要到11就可以 6 const p:array[1..5]of 1..11=(2,3,5,7,11); 7 var i,n,ans:longint; 8 f:array[0..2000005]of longint; 9 function min(a,b:longint):longint; 10 begin 11 if a>b then min:=b else min:=a; 12 end; 13 function work(x:longint):longint; 14 var w,t,i:longint; 15 begin 16 if x=1 then exit(0); //若1*p，则最少是f[p]，而不是f[p]+1 17 if f[x]<>0 then exit(f[x]); 18 work:=maxlongint; 19 for i:=1 to 5 do //枚举素数 20 begin 21 t:=x div p[i]; 22 work:=min(work,min(work(t)+f[x-t*p[i]]+f[p[i]], //用加x=p[i]*t+(x-p[i]*t) 23 work(t+1)+f[t*p[i]+p[i]-x]+f[p[i]])); //用减x=p[i]*(t+1)-((t+1)*p[i]-x) 24 end; 25 f[x]:=work; 26 end; 27 begin 28 assign(input,'one.in');reset(input); 29 assign(output,'one.out');rewrite(output); 30 fillchar(f,sizeof(f),0); 31 for i:=1 to 5 do f[i]:=i; //初始赋值 32 f[6]:=5;f[7]:=6;f[8]:=6;f[9]:=6; 33 f[10]:=7;f[11]:=8; 34 while not eof do 35 begin 36 readln(n); 37 if n>11 then ans:=work(n) else ans:=f[n]; 38 writeln(ans); 39 end; 40 close(input);close(output); 41 end. 42 // By Lambert