递推与动态规划.doc

目录第一章 递推与动态规划2001年普及组第1题-数的计数-ok-2003年提高组第3题-加分二叉树-ok-2000年普及组第3题-乘积最大-ok-2003年普及组第2题-数字游戏-ok-2001年提高组第3题-统计单词个数-ok-1997年普及组第3题-街道路径条数-ok-2002年普及组第4题-过河卒-ok-1997年普及组第1题-统计正方形和长方形个数-ok-1997年提高组第3题-骑士游历-ok-2000年提高组第4题-方格取数-ok-2003年普及组第3题-栈-ok-1996年提高组第3题-挖地雷-ok-1999年提高组第1题-拦截导弹-ok-2004年提高组第3题-合唱队形-ok-2001年普及组第4题-装箱问题-ok- 1996年提高组第4题-砝码秤重-ok-第一章 递推与动态规划2001年普及组第1题-数的计数【问题描述】我们要求找出具有下列性质数的个数(包含输入的自然数n)：先输入一个自然数n（n1000）, 然后对此自然数按照如下方法进行处理：（1）不作任何处理；（2）在它的左边加上一个自然数，但该自然数不能超过原数的一半；（3）加上数后，继续按此规则进行处理，直到不能再加自然数为止。【输入格式】 输入文件count.in中只有一个数n【输出格式】 输出文件count.out只有一行，该行只有一个数，表示求得的满足要求的数的个数。【输入样例】 6【输出样例】6【输入/输出样例说明】输入数字6按以上处理方法，能得到如下的6个数字：6162612636136【官方测试数据】序号输入输出11121014350786410098285198195830【分析】一 题意分析以fi表示i经处理能得到的数的个数。则：11图1 数1处理后,只能得到11如图1所示，1经处理，只能得到1本身（1个数）。因此f1=1；221221图2 数2处理后,得到2、122如图2所示，2经处理，能得到的数的个数f2：（1）2本身（1个数）。（2）2前加1；对1继续处理，能得到的数个数为f1；因此，f2=1+f1=1+1=2。33图3 数3处理后,得到3、1313133如图3所示，3经处理，能得到的数的个数f3：（1）3本身（1个数）。（2）3前加1；对1继续处理，能得到的数个数为f1；因此，f3=1+f1=1+1=2。44图4 数4处理后,得到4、14、24、124141424241212444如图4所示，4经处理，能得到的数的个数f4：（1）4本身（1个数）。（2）4前加1；对1继续处理，能得到的数个数为f1；（3）4前加2；对2继续处理，能得到的数个数为f2；因此，f4=1+f1 +f2=1+1+2=4。5如图5所示，5经处理，能得到的数的个数f5：（1）5本身（1个数）。（2）5前加1；对1继续处理，能得到的数个数为f1；（3）5前加2；对2继续处理，能得到的数个数为f2；因此，f5=1+f1 +f2=1+1+2=4。55图5 数5处理后,得到5、15、25、1251515252512125566图6 数6处理后,得到6、16、26、126、36、1361616262612126636361313666如图6所示，6经处理，能得到的数的个数f6：（1）6本身（1个数）。（2）6前加1；对1继续处理，能得到的数个数为f1；（3）6前加2；对2继续处理，能得到的数个数为f2；（4）6前加3；对3继续处理，能得到的数个数为f3；因此，f6=1+f1 +f2 +f3=1+1+2+2=6。fi=1+f1原数i,只有1个i前加1,1按照规则能产生数的个数+f2i前加2,2按照规则能产生数的个数+ +fi div 2i前加i/2,i/2按照规则能产生数的个数图7 fi的计算公式如图7所示，一般地，对数字i处理后，能得到的数的个数为：fi=1+f1+f2+fi div 2。二如图8所示，求数12经处理后，能得到的数的个数的过程f1f2f1f3f1f2f1f5f4f2f1f2f1f3f6f2f1f3f12f4f5f6图8 f12的计算过程1。计算f1; f1=1；2。由f1计算f2; f2=1+f1=1+1=2；3。由f1计算f3; f3=1+f1=1+1=2；4。由f1、f2计算f4; f4=1+f1 +f2=1+1+2=4；5。由f1、f2计算f5; f5=1+f1 +f2=1+1+2=4；6。由f1、f2、f3计算f6; f6=1+f1 +f2 +f3=1+1+2+2=6；7。由f1、f2、f3、f4、f5、f6计算f12; f12=1+f1 +f2 +f3 +f4 +f5 +f6=1+1+2+2+4+4+6=20；【算法1】1输入n；2f11；3for i2 to n div 2 do计算f2至fn div 24 fi1+f1+f2+fi div 2；5fn1+f1+f2+fn div 2；6输出fn；【参考程序1】program p2001_1(input,output);const maxn=10000;var i,j,n:Integer; f:array1.maxn of longint;begin assign(input,count.in); reset(input); assign(output,count.out); rewrite(output);readln(n); close(input); f1:=1;for i:=2 to n div 2 do begin fi:=1; for j:=1 to i div 2 do fi:=fi+fj; end; fn:=1; for i:=1 to n div 2 do fn:=fn+fi; writeln(fn); close(output);end.【算法的复杂性】求fn的运算次数：1f1:=1的1次；2求fi的二重循环的运算次数不大于：(1+i/2)i=2n/2=(n/2-1) +(n/2+2)(n/2-1)/4=n2/16+5n/8-3/23fn:=1的1次；4求fn的循环的运算次数不大于n/2次：因此合计运算次数不大于：1+ n2/16+5n/8-3/2+1+ n/2= n2/16+9n/8+1/2次。因此此算法的时间复杂度为O(n2)。【算法的改进】一递推式的改进如果输入数据要求n最大规模达到1000000。此时，上述O(n2)的算法在n较大时，必定超时。我们寻找更好的算法。我们将求fi的递推式fi=1+f1+f2+fi div 2作一改进。（1）f2k+1=1+ f1+f2+f(2k+1) div 2 =1+ f1+f2+fk =1+ f1+f2+f(2k) div 2 =f2k； 即f2k+1= f2k（2）f2k+2=1+ f1+f2+fk+1 =1+ f1+f2+fk+fk+1 =f2k+fk+1 即f2k+2= f2k+fk+1二几个实例求解过程1 求f16，如图9所示。f1f2f3f2f2f2f4f2f1f3f16f4f5f6图9 f16的计算过程f5f4f3f4f6f7f6f4f6f8f7f8（1）求初值f1、f2：f1=1；f2=2；（2）求f3 、f4： f3=f3-1=f2=2； f4=f4-2+f4 div 2=f2+ f2=2+2=4；（3）求f5 、f6： f5=f5-1=f4=4； f6=f6-2+f6 div 2=f4+ f3=4+2=6；（4）求f7 、f8： f7=f7-1=f6=6； f8=f8-2+f8 div 2=f6+ f4=6+4=10；（5）求f16： f16= 1+ f1+f2+f3 +f4 +f5 +f6 +f7+f8=1+1+2+2+4+4+6+6+10=36；2求f15（1）求初值f1、f2：f1=1；f2=2；（2）求f3 、f4： f3=f3-1=f2=2； f4=f4-2+f4 div 2=f2+ f2=2+2=4；（3）求f5 、f6： f5=f5-1=f4=4； f6=f6-2+f6 div 2=f4+ f3=4+2=6；（4）求f7 、f8： f7=f7-1=f6=6； f8=f8-2+f8 div 2=f6+ f4=6+4=10；（5）求f15： f15= 1+ f1+f2+f3 +f4 +f5 +f6 +f7 =1+1+2+2+4+4+6+6=26；【算法2】1输入n；2f11；3f22；4s2；5逐对产生f2k+1、f2k+2的值f2k+1f2k和f2k+2f2k+fk+1；6fn1+f1+f2+fn div 2；7输出fn；【参考程序2】program p2001_1(input,output);const maxn=500000;var i,n,m,s:longint; f:array1.maxn of real; g:real; begin assign(input,count.in); reset(input); assign(output,count.out); rewrite(output); readln(n); close(input); f1:=1; f2:=2; m:=n div 2 div 2;其实产生(n div 2-1) div 2对即可 s:=2; for i:=1 to m do产生m对 begins:=s+1; fs:=fs-1;f2k+1s:=s+1;fs:=fs-2+fs div 2;f2k+2 end; g:=1; for i:=1 to n div 2 dog=1+f1+f2+fn div 2 g:=g+fi; writeln(g:0:0); close(output);end.【算法2的复杂性】1时间复杂度： （1）产生m对f2k+1和f2k+2时，fs的计算次数为：2*m=2* (n div 2 div 2)n/2。 （2）产生m对f2k+1和f2k+2时，s类加次数为：2*m=2* (n div 2 div 2)n/2。 （3）产生g（fn）时的循环，计算n div 2n/2。 因此最多计算3n/2次。算法2的时间复杂度为O(n)。2空间复杂度： 需要一个f数组保存中间结果。每个real型数据占8B，因此，需要额外空间为：500000*8B=4000000B4000KB4MB。【问题】上述程序2运行时，n输入最大的值1000000时，输出为： 1.646006492004638E042表示当n=100万时，fn= 1.646006492004638*1042。即f100万有43位数。而real实型最多只有16位有效数字。因此，必须采用高精度数来保存各fi的值。若以1位整数表示10进制的1位数字，43位数，需要一个43元素的数组来保存。则每计算1次fi的值，需计算43次。因此合计计算量为43n。当取100万时，需进行4300万次运算。这在限时1秒的情况下，肯定超时。（当n=100万时，在某机器上，程序2实际测得运行时间为6秒23）。下面的程序3以1位长整型（longint）来表示高精度数的9位数字。每个fi的43位数，可以用5个长整型数来表示。如：（1）1的计数为1，以f1,1=1，f1,2=0，f1,3=0，f1,4=0，f1,5=0；（2）4550的计数为187894009136422，如图10所示，以f4550,1=9136422，f4550,2=187894，f4550,3=0，f4550,4=0，f4550,5=0来表示。000187894009136420020f4550,1f4550,2f4550,3f4550,4f4550,5图10 4550的计数,以5个长整型数表示因为长整型可表示-21亿多至21亿多的数，即它有10位数位。求f2k+2时，f2k+2的第j位= f2k的第j位+ fk+1的第j位+求第j-1位时产生的进位。f2k的第j位和fk+1的第j位都小于10亿，两者相加，小于20亿，在长整型表示范围内。当某位相加和超过999999999时，向下一位进位。处理方法其实类似10进制。我们可以当作10亿进制处理。具体算法参见【参考程序3】。【参考程序3】program p2001_1(input,output);const maxn=500000;type num=array1.5 of longint;以5位长整型来表示1个数var i,j,n,m,s:longint; f:array1.maxn of num; g:num; c:integer;进位值begin assign(input,count.in); reset(input); assign(output,count.out); rewrite(output); readln(n); close(input); 以下2行求得f1=1，以0 0 0 0 1 表示f1,1:=1; for j:=2 to 5 do f1,j:=0; 以下2行求得f2=2，以0 0 0 0 2 表示 f2,1:=2; for j:=2 to 5 do f2,j:=0; m:=n div 2 div 2; s:=2; for i:=1 to m do求得m对f2k+1和f2k+2 begin s:=s+1; for j:=1 to 5 do第1至第5位 fs,j:=fs-1,j;f2k+1的1至5位f2k+1的1至5位s:=s+1;以下7行实现：f2k+2f2k+ fk+1 c:=0;第0位向第1位的进位为0 for j:=1 to 5 do处理第j位加法 beginf2k+2的第j位f2k的第j位+fk+1的第j位+第j-1位向j位的进位 fs,j:=fs-2,j+fs div 2,j+c; c:=fs,j div 1000000000;第j位向下一位的进位值 fs,j:=fs,j mod 1000000000;当前第j位值，去除进位后的剩余 end; end; g1:=1;以下2行，fn=1 for j:=2 to 5 dogj:=0;以下10行，在fn（即g）原值1基础上，加上f1、f2、fn div 2 for i:=1 to n div 2 do每次循环加上fi begin c:=0; 第0位向第1位的进位为0 for j:=1 to 5 do处理第j位加法 begin gj:=gj+fi,j+c;将fi的第j位加至fn上 c:=gj div 1000000000;取得第j位向下一位的进位 gj:=gj mod 1000000000;去除进位后的剩余值 end; end; i:=5;以下4行，输出最高位 while gi=0 do i:=i-1; write(gi); i:=i-1; while (i0) do输出最高位外的其余位 begin if gi10 then只有1位数，补8个0；其余依次类推 write(00000000) else if gi100 then write(0000000) else if gi1000 then write(000000) else if gi10000 then write(00000) else if gi100000 then write(0000) else if gi1000000 then write(000) else if gi10000000 then write(00) else if gi100000000 then write(0); write(gi); i:=i-1; end; writeln; close(output);end.【算法3的复杂性】1时间复杂性： （1）产生m对f2k+1和f2k+2时，fs的计算次数为：2*m*5=10* (n div 2 div 2)5n/2。 （2）产生m对f2k+1和f2k+2时，s类加次数为：2*m=2* (n div 2 div 2)n/2。 （3）产生g（fn）时的循环，计算5*（n div 2）5n/2。 因此最多计算11n/2次。算法3的时间复杂度为O(n)。当n=100万时，最多计算550万次。因此在一秒的时限内，不会超时。2空间复杂性： 每个长整型占4B，因此需额外空间：50万*5*4B=1000万B10000KB10MB。【其它解法】本题的递归解法，参见第 册2003年提高组第3题-加分二叉树【问题描述】设一个n个节点的二叉树tree的中序遍历为（l,2,3,n），其中数字1,2,3,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，树tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分 subtree的右子树的加分subtree的根的分数若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为（1,2,3,n）且加分最高的二叉树tree。要求输出； （1）tree的最高加分 （2）tree的前序遍历【输入格式】 输入文件binary.in的第1行：一个整数n（n30），为节点个数。 第2行：n个用空格隔开的整数，为每个节点的分数（分数100）。【输出格式】 输出文件binary.out的第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。 第2行：n个用空格隔开的整数，为该树的前序遍历。【输入样例】55 7 1 2 10【输出样例】1453 1 2 4 5【官方测试数据】序号输入输出159115 7 8 18 194 2 1 3 52108397015 4 8 9 19 2 1 40 20 227 4 2 1 3 5 6 9 8 10315636679427 38 9 19 2 1 4 2 2 4 5 6 7 8 95 3 1 2 4 12 8 6 7 10 9 11 14 13 1542031735896917 18 9 19 3 1 4 2 2 4 5 6 7 8 9 3 8 4 5 65 3 1 2 4 16 12 8 6 7 10 9 11 14 13 15 18 17 19 205257814952389 8 9 9 5 7 4 2 2 4 5 6 7 8 9 3 3 4 5 1 2 1 2 3 28 4 2 1 3 6 5 7 16 12 10 9 11 14 13 15 20 18 17 19 23 21 22 24 25【分析】采用动态规划算法 以样例数据为例。此时，有5个数依次为5 7 1 2 10；pIp-1p+1J由节点I,I+1,p,J 组成的子树，它的根为p号节点 因为n个数组成的二叉树的中序序列为1，2，,n依次递增排列,所以在该树中, 若某子树由第i个至第j个元素组成，它的根为p,则它的左子树的节点序号均小于p,右子树的节点序号均大于p。(如下图)从第i个至第j个元素构成的所有二叉树中，能取得最高加分值记为fi,j，取得此最高加分时，该树的根序号为ri,j。则针对样例数据，有以下结论：1）最高加分为f1,5；2）取得最高加分时的根为r1,5；3）所有左子树中的元素序号在1至r1,5-1之间；4）所有右子树中的元素序号在r1,5+1至5之间；求fi,j的递推公式如下：fi,j=maxfi,p-1*fp+1,j+fp,p,其中pi,j【样例数据的求解过程】一计算一个元素组成的子树系统15第1元素组成加分二叉树最大值f1,1=5最大值时根序号r1,1=127第2元素组成加分二叉树最大值f2,2=7最大值时根序号r2,2=231第3元素组成加分二叉树最大值f3,3=1最大值时根序号r3,3=342第4元素组成加分二叉树最大值f4,4=2最大值时根序号r4,4=4510第5元素组成加分二叉树最大值f5,5=10最大值时根序号r5,5=5二计算二个元素组成的子树系统27312731第2-3元素组成加分二叉树最大值f2,3=1*1+7=8最大值时根序号r2,3=215271527第1-2元素组成加分二叉树最大值f1,2=1*7+5=12最大值时根序号r1,2=131423142第3-4元素组成加分二叉树最大值f3,4=1*2+1=3最大值时根序号r3,4=34251042510第4-5元素组成加分二叉树最大值f4,5=1*10+2=12最大值时根序号r4,5=4三计算三个元素组成的子树系统第1-3元素组成加分二叉树最大值f1,3=13最大值时根序号r1,3=115f2,3以1号元素为根时最大值为1*8+5=1327f3,3以2号元素为根时最大值为5*1+7=12f1,131f1,2以3号元素为根时最大值为12*1+1=132第2-4元素组成加分二叉树最大值f2,4=15最大值时根序号r2,4=327f3,4以2号元素为根时最大值为1*3+7=1031f4,4以3号元素为根时最大值为7*2+1=15f2,24f2,3以4号元素为根时最大值为8*1+2=10第3-5元素组成加分二叉树最大值f3,5=13最大值时根序号r3,5=331f4,5以3号元素为根时最大值为1*12+1=1342f5,5以4号元素为根时最大值为1*10+2=12f3,3510f3,4以5号元素为根时最大值为3*1+10=13四计算四个元素组成的子树系统第1-4元素组成加分二叉树最大值f1,4=25 最大值时根序号r1,4=315f2,4以1号元素为根时最大值为1*15+5=2027f3,4以2号元素为根时最大值为5*3+7=22f1,131f1,2以3号元素为根时最大值为12*2+1=25f4,442f1,3以4号元素为根时最大值为13*1+2=15第2-5元素组成加分二叉树最大值f2,5=85最大值时根序号r2,5=327f3,5以2号元素为根时最大值1*7+13=2031f4,5以3号元素为根时最大值为7*12+1=85f2,242f2,3以4号元素为根时最大值为8*10+2=82f5,5510f2,4以5号元素为根时最大值15*1+10=25第1-5元素组成加分二叉树最大值f1,5=145 最大值时根序号r1,5=315f2,5以1号元素为根时最大值为1*85+5=9027f3,5以2号元素为根时最大值为5*13+7=72f1,131f1,2以3号元素为根时最大值为12*12+1=145f4,542f1,3以4号元素为根时最大值为13*10+2=132510f1,4以5号元素为根时最大值为25*1+10=35f5,5五计算所有五个元素组成的二叉树系统的最大加分和根因此，最高加分为f1,5=145，获得最高加分时的树根是3号元素。最高加分时的前序序列的构造过程：1。输出序号15的根r1,5=32。输出3号节点的左子树，即序号12的根r1,2=1 2.1。1号节点的左子树为空 2.2。输出1号节点的右子树，即序号2的根r2,2=23。输出3号节点的右子树，即序号45的根r4,5=4 3.1。4号节点的左子树为空 3.2。输出4号节点的右子树，即序号5的根r5,5=5【参考程序】program t2003_3(input,output);const maxn=30;var n,i,j,k,p:integer; r:array1.maxn,0.maxnof integer;节点i至j组成的子树，得到最大加分时的根为ri,j f:array1.maxn,0.maxnof real; 节点i至j组成的子树，得到的最大加分为fi,j first:boolean;输出节点I至j组成的子树的前序序列procedure out(i,j:integer);var k:integer;begin k:=ri,j; if k0 then begin 节点i至j组成的子树非空 if first then 输出根 begin write(k);first:=false;end else write( ,k); out(i,k-1); 输出左子树 out(k+1