信息学集训队作业hqm

1、题目来源：已有算法：搜索，O(n3*logn)的动态规划（正确性有待考证）者：候启明题目描述：已知正整数 n，求用 1、+、-（减号，不能作为负号使用）、*、()算出 n 的最少运算次数。理由：这类题在很多初级的竞赛读物上有不少，书上的算法多为搜索。但这道题的简化版“已知正整数n，求用 1、+、*、()算出 n 的最少运算次数”是可以在 O(n2)的时间内解决的，所以，虽然当时与我的结果是搜索，但后来我仍然觉得这道题可能也可以动态规划，经过几天的思考，终于找到了一个多项式级的算法。但是一来所以仍需严格证明和改进。严格证明，二来次数太高，动态规划算法及初步“证明”：容易证明运算次数等于（运算所用

2、 1 的个数-1）。不妨设算出正整数x 至少需要x 个 1。由于减号的引入带来了问题的后效性，因此先从减号入手，显然有：假如 n 的最优解的最后一步运算为减法，即 n=a-b，其中 an,b0，则有 f(n)=f(a)+f(b)。故对 n 的任何一个可行解，其步数必然大于等于 f(a)+f(b)。作如下定义：如果存在正整数 a、b、n，使得 a-b=n，且 f(n)=f(a)+f(b)，则说 a 对 n 有直接减影响。设对任意的 x 有 g(x)=f(x)=u(x)有 g(y)+g(y-x)h(x)（即对任意的 y=u(x)，y 对 x 没有直接减影响）。做到这里，我猜测有如下命题成立：定义

3、f(n,x)=minf(n,a)+f(n,b)|a+b=x 或 a-b=x 或 a*b=x，a=u(n)，b1， f(n,1)=1，则 f(n)=f(n,n)。根据这一命题，不难得出相应的动态规划算法：1、输入 n。2、计算 u(n)和对 1 到 u(n)所有正整数x 的一个初始可行解的步数 bhx。3、对 1 到u(n)每个正整数 x，依次判断是否存在正整数 a、b，使得 a+b=x 或 a-b=x 或a*b=x且 bha+bhbbhx。如果存在，则将 bhx更新为 bha+bhb。4、如果在 3 中没有更新任何 bhx，算法结束，否则回到 3。函数 g(x)，h(x)，u(x)的一种取法：

4、首先，用二分法可以得到问题的一个至多 3(log(2,x)+1)步的可行解，可取 h(x)=用二分法得到的可行解的步数，有 h(x)=3log(3,x)（表示 n 以 3 为底的对数，下同），可取 g(x)=3log(3,x)。这样，可取 u(x)=2x（显然， g(2x)+g(x)=6log(3,x)+3log(3,2)3log(2,x)+1=h(x)。现在来分析一下复杂度：我在步骤 2 采用二分法计算初始可行解，因此步骤 2 的复杂度只有 O(nlogn)，同后面步骤 3、4相比，完全可以忽略。步骤 3 可以用简单的枚举法在 O(u(n)2)的时间内实现（我还没有找到更快的方法，不过我觉得

5、可能有）。因为每执行一次步骤 3，必然至少有一个 bhx至少减少 1（除了最后一次），而初始时所有 bhx之和不超过 3nlog(2,n)，故步骤 3 至多执行 3nlog(2,n)次，总复杂度上界为 O(u(n)2*n*logn)，因为 u(n)可取 2n，这时复杂度上界为 O(n3*logn)。最后提一句：这种算法的实际效率比理论要高一些，n=2000 时大概只有 3 至 4s 左右，因此怀疑有更好的复杂度上界。附程序：O(n3*logn)progr constroblem2;cc:array0.2 of char=(+,*,-); varn,u,i,j,k:long;bh,d1,d2,d

6、3:array1.5000 ofeger;done:;function greedy(n:long beginif n=5 then greedy:=n greedy:=greedy(n shrend;):long;else 1)+2+(nand1);procedure outso vari:long; beginif n6 then begin write(1); for i:=2 to n:long);dowrite(+1); endelsebegin write();outsolu(d1n);write();write(ccd3n);write();outsolu(d2n);write(

7、); end;end;begin readln(n); u:=n shl 1;for i:=1 to 5 do bhi:=i;for i:=6 to u do begin bhi:=greedy(i); if odd(i) thenbegin d1i:=pred(i); d2i:=1;d3i:=0;end elsebegind1i:=i shr 1;d2i:=2;d3i:=1;end; end;while true do begin done:=true;for i:=6 to u do begink:=i;for j:=1 to pred(i) do begindec(k);if bhj+bhkbhi then begin bhi:=bhj+bhk; d1i:=j;d2i:=k;d3i:=0;done:=false; end;end;for j:=2 to i shr 1 do if i mod j=0 thenbegink:=i div j;if bhj+bhkbhi then begin bhi:=bhj+bhk; d1i:=j;d2i:=k;d3i:=1;done:=false; end;end; k:=0;for j:=succ(i) to u do begininc(k);if bhj+bhkbhi