NOIP基础算法--枚举、递推和递归

NOIP基础算法综合第一部分枚举策略一、枚举法的基本思想枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。枚举结构：循环+判断语句。二、枚举法的条件:虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：⑴可预先确定每个状态的元素个数n；⑵状态元素a1，a2，…，an的可能值为一个连续的值域。三、枚举法的框架结构设ai1—状态元素ai的最小值；aik—状态元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k，ai1≤ai≤aik，……，an1≤an≤ankfora1←a11toa1kdofora2←a21toa2kdo……………………forai←ai1toaikdo……………………foran←an1toankdoif状态(a1，…，ai，…，an)满足检验条件then输出问题的解；枚举法的优点⑴由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解；⑵由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。枚举法的缺点枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。四、枚举法的优缺点“直译”枚举：直接根据题意设定枚举对象、范围和约束条件。注意认真审题，不要疏漏任何条件例题1：砝码称重(noip1996)【问题描述】设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重=1000），求用这些砝码能称出不同的重量个数。【文件输入】输入1g、2g、3g、5g、10g、20g的砝码个数。【文件输出】输出能称出不同重量的个数。【样例输入】110000【样例输出】3【分析】根据输入的砝码信息，每种砝码可用的最大个数是确定的，而且每种砝码的个数是连续的，能取0到最大个数，所以符合枚举法的两个条件，可以使用枚举法。枚举时，重量可以由1g,2g,……,20g砝码中的任何一个或者多个构成，枚举对象可以确定为6种重量的砝码，范围为每种砝码的个数。判定时，只需判断这次得到的重量是新得到的，还是前一次已经得到的，即判重。由于重量=1000g，所以，可以开一个a[1001]的数组来判重。核心参考代码：readln(a,b,c,d,e,f)forc[1]:=0toado//1g砝码的个数forc[2]:=0tobdo//2g砝码的个数forc[3]:=0tocdo//3g砝码的个数forc[4]:=0toddo//5g砝码的个数forc[5]:=0toedo//10g砝码的个数forc[6]:=0tofdo//20g砝码的个数beginsum:=0;fori:=1to6dosum:=sum+c[i]*w[i];a[sum]:=1;//标记end;fori:=1to1000doifa[i]=1theninc(num);//统计不同重量的个数Writeln(num);【问题描述】给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：注意：1.加号与等号各自需要两根火柴棍2.如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C≥0）3.n根火柴棍必须全部用上【输入】输入文件matches.in共一行，又一个整数n（n≤24）。【输出】输出文件matches.out共一行，表示能拼成的不同等式的数目。例题2：火柴棒等式（NOIP2008）例题2：火柴棒等式（NOIP2008）【问题简述】给你n(n=24)根火柴棒,叫你拼出“A+B=C”这样的等式,求方案数。【思路点拨】本题主要考查对枚举法的掌握，可以枚举A和B的取值，考查等式是否刚好用了24根火柴棒。1S的时限对枚举的范围有所要求，必须要仔细分析A和B的取值。例题2：火柴棒等式（NOIP2008）本题最多24根火柴，等号和加号共用4根火柴，所以A,B,C这3个数字需用20根火柴。我们考查A和B的最大的取值可能：0~9这10个数字所用的火柴数为6,2,5,5,4,5,6,3,7,6，很明显数字1用的火柴棒最少只要2根，不妨让B为1，那么A和C最多可以使用18根火柴，而C=A，满足条件的A的最大取值为1111。所以枚举A和B的范围是从0~1111。为了加快速度，可以将0到2222的所有整数需要的火柴棒数目提前算好保存在数组中。五、枚举算法的优化枚举算法的时间复杂度：状态总数*单个状态的耗时。⑴提取有效信息；⑵减少重复计算；⑶将原问题化为更小的问题；⑷根据问题的性质进行截枝；⑸引进其他算法【例题3】给你n(n=105)个整数，然后要有m(m=105)个询问。每个询问两个整数i和j，问第i个数字到第j个数字所有数字之和。【朴素算法】readln(n);fori:=1tondoread(a[i]);fori:=1tomdobeginread(x,y);sum:=0;forj:=xtoydosum:=sum+a[j];writeln(sum);end;时间复杂度为：O(nm)【优化算法】先递推计算出s[i]=s[i-1]+a[i]，再回答询问情况;readln(n);fori:=1tondo{统计求和}beginread(a[i]);s[i]:=s[i-1]+a[i];end;fori:=1tomdobeginread(x,y);writeln(s[y]-s[x-1]);end;【例题4】对于给定的N*M的矩形，在其中找一个R*C的权值最大的区域,1=N,M=1,000。【算法一】：以每一个格子为左上角枚举R*C的区域，并求出它的权值之和。最后取其中的最大值。此算法包含4重循环。时间复杂度：O(N^4)【算法二】：我们设S[i,j]表示以(1,1)为左上角，(i,j)为右下角区域的权值之和，那么我们以(i,j)为右下角的R*C区域权值之和的计算公式为：Area[i,j]=S[i,j]+S[i-R,j-C]-S[i-R,j]-S[i,j-C]其中S[i,j]的计算公式为：S[i,j]=value[i,j]+S[i-1,j]+S[i,j-1]-S[i-1,j-1]你可以随手画图出来，很容易即可证明上面两个式子。最后取Area[]中的最大值即可。时间复杂度：O(N^2)【例题5】最大连续子序列的和【问题描述】给你一个有n(n=100000)个整数的序列，要求你求出其中最大连续子序列的和。【算法1】枚举起始位置，结束位置，计算中间的和。时间复杂度O(n^3)。maxx:=a[1];fori:=1tondoforj:=itondobeginsum:=0;fork:=itojdosum:=sum+a[k];ifsummaxxthenmaxx:=sum;end;【算法2]：优化的枚举——O(n^2)s[0]:=0;fori:=1tondos[i]:=s[i-1]+a[i];//初始化求和maxx:=a[1];fori:=1tondoforj:=itondoifs[j]-s[i-1]maxxthenmaxx:=s[j]-s[i-1];时间复杂度：预处理+主程序=O(n+n^2)=O(n^2)，n=5000【算法3】分治——O(nlogn)、最大连续子序列的位置有三种可能：①完全处于序列的左半；②完全处于序列的右半；③跨越序列中间；【算法4】DP——O(n)1、阶段和状态：以第i个数结尾的最大连续子序列的和，只存在两种选择：情形1：只包含a[i]情形2：包含a[i]和以a[i-1]结尾的最大连续和序列故设f[i]表示以a[i]结尾的最大连续子序列的和2、状态转移方程：转移方程：f[i]=max{a[i],f[i-1]+a[i]}(2=i=n)初始化：f[1]=a[1]Answer=max{f[i]|1=i=n}【例题6】最大子矩阵问题【问题描述】给定一个二维的数组（含正数或负数），请从中找出和最大的子矩阵。例如：1、“直译”枚举过程Forx1:=1tondo//枚举矩形左上角(x1,y1)fory1:=1tondoforx2:=1tondo//枚举矩形右下角(x2,y2)fory2:=1tondo//考察状态左上角为(x1,y1)右下角为(x2,y2)内矩形的元素之和；beginsum:=0；forx:=x1tox2do//计算当前矩形内元素的和fory:=y1toy2dosum:=sum+a[x,y]；ifsumbestthenbest:=sum；//调整最优解end;这个算法相当粗糙，枚举状态的费用为O(n6)(x1,y1)(x2,y2)2、从减少重复计算入手有刚才一维情况可以推广到二维，在统计左上角为(x1,y1)右下角为(x2,y2)内矩形的元素之和时，我们同样可以先初始化，计算出左上角为(1,1)，右下角为(x,y)内矩形的元素之和s[x][y]。fori:=1tondo//枚举矩形右下角，求和forj:=1tondobeginread(a[i,j]);s[i,j]:=s[i-1,j]+s[i,j-1]-s[i-1,j-1]+a[i,j];end;对于状态左上角为(x1,y1),右下角为(x2,y2)内矩形的元素之和，可以改为：sum:=s[x2,y2]-s[x1-1,y2]-s[x2,y1-1]+s[x1-1,y1-1];ifsumbestthenbest:=sum；//调整最优解由于先进行了预处理，整个算法的时间复杂度降为O(n4)3、提取恰当的信息容易观察到，最大子矩阵问题是最大连续子序列和问题的提升，即将一条线换成一个面，将一维问题提升到二维问题。所以我们计算最大子矩阵的方法就是将一行行的数进行累加以求得最大值。但是还有一个问题，那就是应该如何高效地存储矩阵？我们可以想到：在一个一维的数列中，设数组b[i]表示从第1个元素到第i个元素的和，则如果想要求第i个元素到第j个元素的和，只需要计算b[j]-b[i-1]的值就行了。由此推广到二维矩阵，设b[i,j]表示矩阵第j列前i个元素的和，a[i,j]表示元素数据，则压缩存储：fori:=1tondoforj:=1tondobeginread(a[i,j]);b[i,j]:=b[i-1,j]+a[i,j];}因此，我们可以使用三重循环求出所有的矩形值，即枚举起始行i和终止行j，压缩子矩形成为一行，变成一维求最大子段和问题。即t[k]=max(t[k-1],0)+b[j,k]-b[i-1,k];时间复杂度为O(n3)0-2-7092-62-41-41-180-20-2-7090-13251-17349-171②核心代码sum:=-99999999;//置初值fori:=1tondo//阶段:起始行beginforj:=itondo//状态:结束行begint[1]:=b[j,1]-b[i-1,1];//初始化第1列的值fork:=2tondo//决策:第几列beginift[k-1]0thent[k]:=t[k-1]+b[j,k]-b[i-1,k]elset[k]:=b[j,k]-b[i-1,k];ift[k]sumthensum:=t[k];end;end;end;writeln(sum);六、局部枚举例题7：求第一、第二、第三最短路问题例题8：新年好重庆城里有n个车站，m条双向公路连接其中的某些车站。每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路上花费的时间等于路径上所有公路需要的时间之和。佳佳的家在车站1，他有五个亲戚，分别住在车站a,b,c,d,e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？数据范围：n(n=50,000),m(m=100,000)算法框架为：