基础算法综合

基础算法综合长沙市第一中学曹利国第一部分枚举策略枚举枚举：是对一个问题找出所有的可行状态，然后从中找出最优的状态。枚举的不足：当枚举的状态很多时，所用的时间会非常大，效率比较低。枚举方法的优化枚举算法的时间复杂度：状态总数*单个状态的耗时主要优化方法：⑴减少状态总数⑵降低单个状态的考察代价优化过程从以下几个方面考虑：⑴枚举对象的选取⑵枚举方法的确定

⑶采用局部枚举或引进其他算法例题1：侦探推理（Noip试题）xx同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，xx的同学们先商量好由其中的一个人充当罪犯（在xx不知情的情况下），xx的任务就是找出这个罪犯。接着，xx逐个询问每一个同学，被询问者可能会说：

例题1：侦探推理证词中出现的其他话，都不列入逻辑推理的内容。xx所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。现在，xx需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！数据范围：M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100），M为总人数，P为总共说了多少话例题1：侦探推理初步分析：开始接触的这题目，不知道怎么下手，但是我们从题目中可以知道：凶手只有一个,并且说话的总人数很少深入分析：我们不妨换一个思路，枚举凶手是哪个和今天是星期几；然后对每一句话进行判断，看这个人是不是始终说真话和假话；统计始终说真话和假话的人有多少；最后看是不是符合题目的要求。例题1：侦探推理伪代码：For(longi=1;i<=m;i++)//枚举凶手是谁For(longday=1;day<=7;day++)//枚举今天是星期几{For(longk=1;k<=p;k++)check(k)//判断第K句话是真话还是假话For(longk=1;k<=m;i++)count(i)//统计第k个人是否始终说真话或假话。Getcheck()//看这个枚举的结果是不是符合题目要求

}例题2B_station在离著名的国家Berland不远的地方，有一个水下工作站。这个工作站有N层。已知：是第i层装有Wi的水，最多可以容纳Li的水，恐怖分子炸毁第i层的代价是Pi。第i层一旦被炸毁，该层所有的水都将倾泻到第i+1层。如果某一层的水量超过了它的容量(即Li)，那么该层就将自动被毁坏，所有的水也会倾泻到下一层。Pivland的恐怖分子想要用最少的钱毁掉第N层，现在他雇佣你来计算，需要炸毁哪些层。

输入:第一行有一个自然数N(1<=n<=15000)。接下来的N行，每行3个整数Wi,Li,Pi(0<=Wi,Li,Pi<=15000)。输出:输出需要炸毁的层的编号。样例Input样例output311000100012010002210100

分析令Si=W1+W2+…+Wi（特别的S0=0）。不妨设恐怖分子炸毁的第高层是第p层（第一层是最高层，第N层是最底层）。因为恐怖分子的目标是毁灭第N层，所以水必须从第p层一直泻下去。如果存在一个i，满足Wp+Wp+1+…+Wi-1+Wi<=Li，也就是说前面几层的水全部泄下来也无法把第i层自动冲毁，那么就必须要使用炸药把它炸开了。所以恐怖分子需要炸毁的层的集合就是Bomb[p]={p}∪{i|i>pSi-Sp-1<=Li}令Qi=Si-Li，那么：Bomb[p]={p}∪{i|i>pQi<=Sp-1}我们枚举p，然后看哪些层需要炸毁。这样就得到了一个O(n2)的算法。

优化注意到Sp是随着p的增加而递增的，观察两个集合：Bomb[p]={p}∪{i|i>pQi<=Sp-1}Bomb[p-1]={p-1}∪{i|i>p-1Qi<=Sp-2}因为Sp-2<=Sp-1，所以{i|i>p-1Qi<=Sp-2}包含于Bomb[p]，也就是说，Bomb[p-1]是在Bomb[p]的基础上，通过以下操作得到的：删除所有的i∈Bomb[p]，Qi>Sp-2。添加p-1。针对这两种操作，我们可以使用大根堆(Heap)。从大到小枚举p，对于每一个p，执行：Step1.如果堆的根i满足Qi>Sp-2，那么删除根；否则转Step3。Step2.转Step1。Step3.添加p-1。每层至多进堆一次、出堆一次，所以总的时间复杂度是O(nlogn)。对于n<=15000的范围完全能够胜任了。

枚举对象的确定例题3：二进制数的分类若将一个正整数转化为二进制数后，0的个数多于1的个数的这类数称为A类数，否则称为B类数。例如：（13）10=（1101）2，13为B类数；（10）10=（1010）210为B类数；（24）10=（11000）224为A类数；程序要求：求出1～1000之中（包括1与1000），全部A、B两类数的个数。【分析】此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅为1～1000，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。枚举算法的应用例题4：01统计将问题的数据规模扩充到求1到m（m<=1030）中A类数的个数。分析本题是统计问题，但使用1~m的循环来逐个判断显然耗时过多，对于m较大时无法在规定的时间内出解。所以我们希望通过分类统计的方法，进一步抽象问题，得到可行的算法:根据二进制数的前缀来分类是合理的，既没有重复也没有遗漏。当m的二进制数长度为n时，最多有2n种类型，即2（log2m+1）

种，比穷举m种类型有了很大进步。设m=(112)10=(1110000)2，求1~m的A类数个数。可以将112个数分为以下几类：数字形式为(111xxxx)2

这一类数只有1个，即(1110000)2，是A类数数字形式为(110xxxx)2

设4个填数位置填0的个数为S0，填1的个数为S1，则S0+S1+3=7,若为A类数，则S0+1>S1+2,可以取S0=4S1=0；S0=3S1=1.这一类数中的A类数个数：(44)+(34)数字形式为(10xxxxx)2设5个填数位置填0的个数为S0，填1的个数为S1，则S0+S1+2=7若为A类数，则S0+1>S1+1,可以取S0=5S1=0；S0=4S1=1；S0=3S1=2.这一类数中的A类数个数：(55)+(45)+(35)数字形式为(0xxxxxx)2这一类数字的分析与前几类略有不同，因为前几类二进制数的位数都是7，而这一类数还需对位数进行讨论：（1）1位数，即(1)2，不是A类数（2）2位数，即(1x)2，(10)2和(11)2都不是A类数（3）3位数，即(1xx)2，A类数个数为(22)=1（4）4位数，即(1xxx)2，A类数个数为(33)=1（5）5位数，即(1xxxx)2，A类数个数为(44)+(34)=5（6）6位数，即(1xxxxx)2，A类数个数为(55)+(45)=6最后的答案是1+5+16+(1+1+5+6)=35局部枚举例题5：求第一、第二、第三最短路问题局部枚举例题6：新年好重庆城里有n个车站，m条双向公路连接其中的某些车站。每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路上花费的时间等于路径上所有公路需要的时间之和。佳佳的家在车站1，他有五个亲戚，分别住在车站a,b,c,d,e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？分析这一题中的边数远小于n2，所以复杂度也只有nlogn+m算法框架是：（1）用5次最短路，计算出6个点两两之间的距离（2）枚举5个结点的全排列，找到一个使得总路程长度最短的方案。第二部分递推策略递推的概念与基本思想

给定一个数的序列H0,H1,…,Hn,…若存在整数n0，使当n>n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0<i<n)联系起来，这样的式子就叫做递推关系。解决递推问题的一般步骤

建立递推关系式确定边界条件递推求解

递推的形式顺推法和倒推法递推的应用分类

一般递推问题组合计数类问题一类博弈问题的求解动态规划问题的递推关系递推的应用（一般递推问题）例题1:Hanoi塔问题

.

Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上：(1)一次只能移一个圆盘；(2)圆盘只能在三个柱上存放；(3)在移动过程中，不允许大盘压小盘。问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？abc

图1递推的应用（一般递推问题）例题1:Hanoi塔问题

.

Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上：(1)一次只能移一个圆盘；(2)圆盘只能在三个柱上存放；(3)在移动过程中，不允许大盘压小盘。问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？abc

图1分析设hn为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c柱；最后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=3。以此类推，当a柱上有n(n>=2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。∴hn=2hn-1+1

边界条件：h1=1递推的应用（一般递推问题）例2：实数数列一个实数数列共有n项，已知ai=(ai-1-ai+1)/2+d，(1<i<n)(n<60)键盘输入n，d，a1，an，m，输出am。输入数据均不需判错。分析根据公式ai=(ai-1-ai+1)/2+d变形得，ai+1=ai-1-2ai+2d，因此该数列的通项公式为：ai=ai-2-2ai-1+2d，已知a1，如果能求出a2，这样就可以根据公式递推求出am∵ai=ai-2-2ai-1+2d……(1) =ai-2-2（ai-3-2ai-2+2d）+2d=-2ai-3+5（ai-4-2ai-3+2d）-2d=5ai-4-12ai-3+8d……

一直迭代下去，直到最后，可以建立ai和a1与a2的关系式。分析设ai=Pia2+Qid+Ria1，我们来寻求Pi,Qi,Ri的变化规律。∵ai=ai-2-2ai-1+2d∴ai=Pi-2a2+Qi-2d+Ri-2a1-2（Pi-1a2+Qi-1d+Ri-1a1）+2d=(Pi-2-2Pi-1)a2+(Qi-2-2Qi-1+2)d+(Ri-2-2Ri-1)a1∴Pi=Pi-2-2Pi-1 ……② Qi=Qi-2-2Qi-1+2 ……③ Ri=Ri-2-2Ri-1

……④显然，P1=0Q1=0R1=1（i=1） P2=1Q2=0R2=0 （i=2）将初值P1Q1R1和P2Q2R2代入②③④可以求出PnQnRn∵an=Pna2+Qnd+Rna1∴a2=(an-Qnd+Rna1)/Pn然后根据公式①递推求出am，问题解决。改进算法但仔细分析，上述算法有一个明显的缺陷：在求由于在求a2要运用除法，因此会存在实数误差，这个误差在以后递推求am的过程又不断的扩大。在实际中，当m超过30时，求出的am就明显偏离正确值。显然，这种算法虽简单但不可靠。为了减少误差，我们可设计如下算法：∵ai=Pia2+Qid+Ria1 =Pi-1a3+Qi-1d+Ri-1a2 =Pi-2a4+Qi-2d+Ri-2a3……=Pi-2+kak+Qi-2+kd+Ri-2+kak-1∴an=Pn-k+2ak+Qn-k+2d+Rn-k+2ak-1ak=(an-Qn-k+2d+Rn-k+2ak-1)/Pn-k+2……⑤根据公式⑤，可以顺推a2、a3、…、aM。虽然仍然存在实数误差，但由于Pn-k+2递减，因此最后得出的am要比直接利用公式①精确得多。递推的应用（一般递推问题）例题：贮油点。一辆重型卡车欲穿过1000公里的沙漠，卡车耗汽油为1升/公里，卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点，使卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？每一贮油点应存储多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。格式如下：No.Distance(k.m.)Oil(litre)1××××2××××…

……

……分析设Way[i]——第i个贮油点到终点（i=0）的距离；oil[i]——第i个贮油点的贮油量；我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。从贮油点i向贮油点i+1倒推的方法是：卡车在贮油点i和贮油点i+1间往返若干次。卡车每次返回i+1点时应该正好耗尽500公升汽油，而每次从i+1点出发时又必须装足500公升汽油。两点之间的距离必须满足在耗油最少的条件下，使i点贮足i*500公升汽油的要求（0≦i≦n-1）。倒推第一步第一个贮油点i=1应距终点i=0处500km，且在该点贮藏500公升汽油，这样才能保证卡车能由i=1处到达终点i=0处，这就是说Way[1]=500；oil[1]=500；倒推第二步 为了在i=1处贮藏500公升汽油，卡车至少从I=2处开两趟满载油的车至i=1处，所以i=2处至少贮有2*500公升汽油，即oil[2]=500*2=1000；另外，再加上从i=1返回至i=2处的一趟空载，合计往返3次。三次往返路程的耗油量按最省要求只能为500公升，即d1,2=500/3km，Way[2]=Way[1]+d1,2=Way[1]+500/3倒推第三步为了在I=2处贮藏1000公升汽油，卡车至少从I=3处开三趟满载油的车至I=2处。所以I=3处至少贮有3*500公升汽油，即oil[3]=500*3=1500。加上I=2至I=3处的二趟返程空车，合计5次。路途耗油亦应500公升，即d23=500/5，Way[3]=Way[2]+d2,3=Way[2]+500/5；倒推第k步……为了在i=k处贮藏k*500公升汽油，卡车至少从i=k+1处开k趟满载车至i=k处，即oil[k+1]=(k+1)*500=oil[k]+500，加上从i=k返回i=k+1的k-1趟返程空间，合计2k-1次。这2k-1次总耗油量按最省要求为500公升，即dk,k+1=500/(2k-1)Way[k+1]=Way[k]+dk,k+1=Way[k]+500/(2k-1)；i=n的情形i=n至始点的距离为1000-Way[n],oil[n]=500*n。为了在i=n处取得n*500公升汽油，卡车至少从始点开n+1次满载车至I=n，加上从I=n返回始点的n趟返程空车，合计2n+1次，2n+1趟的总耗油量应正好为（1000-Way[n]）*(2n+1)，即始点藏油为oil[n]+(1000-Way[n])*(2n+1)。扫雷(Mine)有一个长度为n的格子，其中某些格子中有一个地雷。给定一个长度为n的非负整数序列，序列中的第i个元素表示第i-1格，第i格，第i+1格（如果存在）中雷的个数。求出地雷的分布方案数。输入文件：

第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<=N<=10000）输出文件：

一个数，即第一列中雷的摆放方案数。SampleInput21

SampleOutput2分析按照我们平时玩扫雷的心得，我们往往可以通过某个位置周围的数字以及已经得到的雷的分布推出其是不是雷。该题同样可以这样做，如果已知第i-1格和i-2格是否有雷(i>2)，则可以通过序列中第i-1个数推出第i格是否有雷。而第2格的状态则只需要由第一格的雷和序列第一个数推出。

设Ai表示序列中第i个元素，Fi表示第I格的雷数,我们可以递推求解。

方程：Fi=Ai-1-Fi-1(i=2)

Fi=Ai-1-Fi-2-Fi-1(i>=3)但是F1的值还是未知的，由于每一格就是有雷和无雷两种状态，显然我们可以枚举第一格雷的状态，即F1的值为0或者1，这样就可以递推得到所有的F值。如果Fi（1<=i<=n）的值不为0，1的话显然是不符合要求的，而如果Fn+Fn-1<>An,显然也是不符合要求的。如果不出现这种情况就得到一种可行的分布方案，所以最后答案不外乎0，1，2三种。

例题3：走直线棋问题。有如下所示的一个编号为１到ｎ的方格：

现由计算机和人进行人机对奕，从１到ｎ，每次可以走ｋ个方格，其中ｋ为集ｓ={a1,a2,a3,....am}中的元素(m<=4)，规定谁最先走到第n格为胜，试设计一个人机对奕方案，摸拟整个游戏过程的情况并力求计算机尽量不败。递推的应用（博弈问题）12345……N-1N题设条件：若谁先走到第N格谁将获胜，例如，假设S={1,2}，从第N格往前倒推，则走到第N-1格或第N-2格的一方必败，而走到第N-3格者必定获胜，因此在N，S确定后，棋格中每个方格的胜、负或和态（双方都不能到达第N格）都是可以事先确定的。将目标格置为必胜态，由后往前倒推每一格的胜负状态，规定在自己所处的当前格后，若对方无论走到哪儿都必定失败，则当前格为胜态，若走后有任一格为胜格，则当前格为输态，否则为和态。分析设1表示必胜态，-1表示必败态，0表示和态或表示无法到达的棋格。例如，设N＝10，S＝{1,2}，则可确定其每个棋格的状态如下所示：而N＝10，S＝{2,3}时，其每格的状态将会如下所示：

有了棋格的状态图后，程序应能判断让谁先走，计算机选择必胜策略或双方和（双方均不能到达目标格）的策略下棋，这样就能保证计算机尽可能不败。分析1-1-11-1-11-1-110-1-1010-1-101在一个n×m的方格中，m为奇数，放置有n×m个数，如图,方格中间的下方有一人，此人可按照五个方向前进但不能越出方格,见右下图。人每走过一个方格必须取此方格中的数。要求找到一条从底到顶的路径，使其数相加之和为最大。输出和的最大值。1643126034-56700260-1-236853400-27-17407-560-1341242人

递推的应用（动态规划中的递推例4：方格取数分析我们用坐标(x,y)唯一确定一个点，其中(m,n)表示图的右上角，而人的出发点是，受人前进方向的限制，能直接到达点(x,y)的点只有(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)。到点(x,y)的路径中和最大的路径必然要从(m/2,0)到(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)的几条路径中产生，既然要求最优方案，当然要挑一条和最大的路径，关系式如下：Fx,y=Max{Fx+2,y-1,Fx+1,y-1,Fx,y-1,Fx-1,y-1,Fx-2,y-1}+Numx,y，其中Numx,y表示(x,y)点上的数字。边界条件为：动态规划与递推的关系上题实质上是采用动态规划来求解,那么与递推动态规划之间到底是什么关系呢？我们不妨画个图(如下图)。而通常人们理解的递推关系就是一般递推关系，故认为动态规划与递推关系是两个各自独立的个体。动态规划一般递推关系递推关系动态规划与递推的关系1、一般递推边界条件很明显,动态规划边界条件比较隐蔽,容易被忽视2、一般递推数学性较强,动态规划数学性相对较弱

3、一般递推一般不划分阶段,动态规划一般有较为明显的阶段第三部分贪心方法贪心方法的基本思想

贪心是一种解题策略，也是一种解题思想使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优利用贪心策略解题，需要解决两个问题：该题是否适合于用贪心策略求解如何选择贪心标准，以得到问题的最优解

适用于贪心策略求解的问题的特点

适用于贪心策略求解的问题必须具有最优子结构的性质，但并不是所有具有最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法——动态规划（例如“0-1背包问题”与“部分背包问题”）

贪心方法的应用例题1：节点网络。现有一个N！个节点的网络，每个节点的编号都是编号（A1A2A3…AN）序列的一个置换。对于任意两个节点S和T，如果T的编号是由S编号的首位与除首位外的编号中任一位交换所得，则S和T之间有一条边，求从给定节点S走到节点（A1A2A3…AN）所需经过的最少边数。其中，n≤100。贪心方法的应用例如n=3的情况：(A1A2A3)(A1A3A2)(A2A3A1)(A2A1A3)(A3A1A2)(A3A2A1)贪心方法的应用【分析】从题意表面上看，本题是一个求最短路径的问题，但题设中的N≤100，也就是说图中最多有100！个节点，采用二维关系的图结构根本无法存贮这众多的状态。通过问题的本质分析，可以将问题转化为一个序列的最优转化问题。贪心方法的应用采用贪心策略：每次让一个节点归位或为下一步工作做准备。其具体步骤为：若序列中第一个点为Ax(x≠1)，则将第一个点和第x个点交换。这便完成了让一个点归位的工作；若第一个是A1，则任找一个编号与位置不相符的点，并与之交换。这样下一步便可让交换到1号位置的点归位。贪心方法的应用(A3A4A1A2)(A1A4A3A2)第一个点A1已归位，但第二个点为A4≠A2，将第2个点A4与A1交换第一个点为A3≠A1，将第3个点A1与A3交换(A4A1A3A2)第一个点为A4≠A1，将第4个点A2与A4交换(A2A1A3A4)第一个点为A2≠A1，将第2个点A1与A2交换(A1A2A3A4)已经符合要求了一共经过4步完成。下面看一个n=4，初始序列为(A3A4A1A2)的推演过程：例题2排序问题排序是计算机科学中一个常见任务。有一种特殊的排序，最多只有3个关键字。例如，试图对这次竞争的奖牌榜排序时，就只有3个关键字，所有的金牌获得者在最前面，随后是获银牌者，最后是铜牌获得者。

本题中用1,2,3分别表示3个关键字，需将它们按升序排列。排序是通过一系列对换操作实现的。一次操作可以交换两个数的位置。子任务A

请写一个程序，对于一个给定的只含有关键字的序列，计算最少需要几次对换操作就可以将其按升序排列。子任务B

输出一种最少次数的对换方案。分析如果要我们自己来手算的话，势必会先找到一对数，使其交换位置后正好都回到应该在的位置，例如数串111232333，我们发现第5位上的3与第6位上的2正好反过来了。把它们交换就可以得到排序后的数串。又因为这样的一次交换使两个数回到正确的位置，这说明这次交换已经发挥了它的最大功效，一定不是多余的，虽然是要求最少的交换次数也绝不能少了这样的交换。到这里我们发现这道题可以用贪心法来做。不断地寻找这样的一对数，直至找不到为止。但是注意，还有一种更加普遍的情况我们没有考虑，也就是虽然存在错位了的数，但是找不到互换位置可以符合以上要求的两个数。例如：113221332中，第3位上的3，第6位上的1，第9位上的2，都是错位的，但不管取他们三个中的哪两个交换，通通都不能使两个数都归原位。这个时候，我们只好放弃一个，只保证一个数可以归原位，于是交换1与2，数串变成113222331，这时再交换3与1，就用两次交换对该数列排完了序。问题变形给定N个不同的正整数，每次只能交换两个相邻的数，如何一住校的交换次数使得其变成升序？贪心方法的应用（贪心标准）例题：d-规则问题。对任意给定的m(m∈N+)和n(n∈N+)，满足m<n，构造一初始集合：P={x|m≤x≤n,x∈N+}(m,n≤100)现定义一种d规则如下：若存在a∈P，且存在K∈N+,K>1，使得Ka∈P，则修改P为：P=P-{y|y=sa,s∈N+}

，并称该d规则具有分值a。现要求编制一个程序，对输入的m,n值，构造相应的初始集合P，对P每应用一次d规则就累加其相应的分值，求能得到最大累加分值的d规则序列，输出每次使用d规则时的分值和集合p的变化过程。贪心方法的应用【分析】初看这一问题，很容易想到用贪心策略来求解，即选择集合中最大的可以删除的数开始删起，直到不能再删除为止，而且通过一些简单的例子来验证，这一贪心标准似乎也是正确的，例如，当m=3，n=10时，集合P＝{3,…,10}，运用上述“贪心标准”可以得到这一问题的正确的最优解d=5＋4＋3＝12，即其d-规则过程如下：1.a=5P={3,4,6,7,8,9} d=52.a=4P={3,6,7,9} d=5+4=93.a=3p={7} d=5+4+3=12贪心方法的应用但是，如果再仔细地分析一个例子，当m=3，n＝18时，如果还是使用上述“贪心标准”，则得到问题的d-规则总分为d=35，其d-规则序列为（9,8,7,6,5），而实际上可以得到最大d-规则总分为d＝38，其对应的d-规则序列为（9,8,7,6,3,5）。为什么会出现这样的反例呢？这是因为，问题中要使得d-规则总分d值越大，不光是要求每一个d分值越大越好，也要求取得的d分值越多越好。因此，本题不能采用纯粹的贪心策略求解。贪心方法的应用【改进】将原算法基础上进行改进。下面给出新的算法：建立集合P={m..n}从ndiv2到m每数构造一个集合c[i]，包含该数在P中的所有倍数（不包括i本身）从ndiv2起找到第一个元素个数最少但又不为空的集合c[i]在d分值中加上i把i及c[i]集合从P集中删除，更新所有构造集合的元素检查所有构造集合，若还有非空集合，则继续3步骤，否则打印、结束贪心方法的应用下面看m=3,n=18时的推演过程：初始P={3..18}找到i=9,c[i]={18},P={3..8,10..17}找到i=8,c[i]={16},P={3..7,10..15,17}找到i=7,c[i]={14},P={3..6,10..13,15,17}找到i=6,c[i]={12},P={3..5,10,11,13,15,17}找到i=3,c[i]={15},P={4,5,10,11,13,17}找到i=5,c[i]={10},P={4,11,13,17}到此所有构造集合全部为空，d=9+8+7+6+3+5=38例题分析：田忌赛马问题

中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马，每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多的钱？正整数n(n<=2000)，表示双方马的数量。分析不妨用贪心思想来分析一下问题。因为田忌掌握有比赛的“主动权”，他总是根据齐王所出的马来分配自己的马，所以这里不妨认为齐王的出马顺序是按马的速度从高到低出的。由这样的假设，我们归纳出如下贪心策略：1、如果田忌剩下的马中最强的马都赢不了齐王剩下的最强的马，那么应该用最差的一匹马去输给齐王最强的马。2、如果田忌剩下的马中最强的马可以赢齐王剩下的最强的马，那就用这匹马去赢齐王剩下的最强的马。

3、如果田忌剩下的马中最强的马和齐王剩下的最强的马打平的话，可以选择打平或者用最差的马输掉比赛。光是打平的话，如果齐王马的速度分别是123，田忌马的速度也是123，每次选择打平的话，田忌一分钱也得不到，而如果选择先用速度为1的马输给速度为3的马的话，可以赢得200两黄金。光是输掉的话，如果齐王马的速度分别是13，田忌马的速度分别是23，田忌一胜一负，仍然一分钱也拿不到。而如果先用速度为3的马去打平的话，可以赢得200两黄金。

通过上述的三种贪心策略，我们可以发现，如果齐王的马是按速度排序之后，从高到低被派出的话，田忌一定是将他马按速度排序之后，从两头取马去和齐王的马比赛。有了这个信息之后，动态规划的模型也就出来了！Dp求解设f[i,j]表示齐王按从强到弱的顺序出马和田忌进行了i场比赛之后，从“头”取了j匹较强的马，从“尾”取了i-j匹较弱的马，所能够得到的最大盈利。状态转移方程如下：F[I,j]=max{f[i-1,j]+g[n-(i-j)+1,i],f[i-1,j-1]+g[j,i]}其中g[i,j]表示田忌的马和齐王的马分别按照由强到弱的顺序排序之后，田忌的第i匹马和齐王的第j匹马赛跑所能取得的盈利，胜为200，输为－200，平为0。贪心方法的应用（贪心标准证明）例题：射击竞赛射击的目标是一个由RC(2≤R≤C≤1000)个小方格组成的矩形网格。每一列恰有2个白色的小方格和R-2个黑色的小方格。行从顶至底编号为1~R，列从左至右编号为1~C。射击者可射击C次。在连续的C次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。如果存在正确的射击方法，则要求找到它。贪心方法的应用射击的选择有2C种，符合要求的却很少。要解决问题，还需从正确的射击方法的特征入手。贪心方法的应用【方法一】网络流算法我们将表示列的点编号为1到C，表示行的点编号为C+1到C+R，如果一个白色方格处在第i行第j列，那么从点j向点C+i连一条弧，弧的容量为1。再增设一个源点S，从点S往点1到C间各连一条弧，弧的容量为1，又设一个汇点T，从点C+1到点C+R向汇点T连一条弧，弧的容量为1，那么从源点S到汇点T求最大流，求出的最大流量即为最多可以射击到的行数。各条流的路线则描述了具体的射击方案。可以看出，如果用网络流求出的最大流量比R小，则问题无解，否则我们可以先根据网络流的结果求出该二分图的具体匹配方案。贪心方法的应用红色的连线流量为1蓝色的连线流量为0选择的射击格即为：(1,3),(2,1),(3,2),(4,4)S21432143T列:行:源:汇:贪心方法的应用网络流算法经过优化，时间复杂度可以达到O(C(n+4C+4R))

上述网络流算法虽然可以通过全部数据，但编程复杂度很高，而且极易出错，一不小心就会因为一个小错误影响整个程序。贪心方法的应用【方法二】贪心方法统计所有行包含的白格数从还没有射击格的行中选出一个白格数最少的检查所选的行若所选行的白格数为0，则输出无解；否则从所选行的白格中任选一个作为射击格，并将与该格同列的另一个白格所处行的白格数减1返回到第2步，直到所有的行都有射击格。若还有列没有选射击格，则在该列任选一白格作为射击格即可贪心方法的应用上面的贪心方法非常高效：时间复杂度为O(RC)，如果在程序中使用堆优化，时间复杂度将降为O(Rlog2C)。空间复杂度是线性的，而且非常容易实现。现在关键的问题就是——如何证明它的正确性？贪心方法的应用【证明】用h[i]表示第i行的白格数。如果最开始的时候：min{h[i]}=0:第i行已经没有办法找到可作为射击格的白格，那么问题只能无解。min{h[i]}=1:那么第i行的这一个白格必须要作为射击格，否则将因第i行没有射击格而造成问题无解。min{h[i]}≥2:那么在这一行任选一个白格，顶多只会造成剩余行中有一行h值为1，再处理那一行，最多也只会再造成剩余行中有一行h值为1，如此往复，将保持h值为1的行数不超过1行，最后最坏的情况也是造成最后一行的h值为1，继续下去所有行就都已选取了射击格了。因此，如果原问题有解，该贪心方法一定能找到一种正确的方案。由此可以证明，此贪心方法是正确的。例题分析买彩票(tickt.exe)电视里面正放着“抽百万大奖，赢幸福生活”的宣传广告，bird看后也想去试试手气，当然，作为经济学院的高材生，他可不屑只是单纯的去碰运气。经过他的一番分析，发现，商家在彩票里面做了手脚，使得每个抽奖点的中奖概率不是完全一样的，而且随着时间的变化而变化，不过这种变化是有规律的。

对于第I个抽奖点，最开始的中奖概率是百万分之Pi，以后每抽一张彩票后都要重新排队，花费的时间是T分钟，每抽一次减少的概率为Di。由于可怜的bird还有一大堆的作业没做，他只能抽出H个小时去买彩票。由于抽奖地点都在一路公共汽车的线路上，所以怕麻烦的bird决定按车站顺序抽奖。当然，bird可以从任意一站开始抽奖，对于经过的抽奖点可以买彩票，也可以不买。假设从第I个抽奖点到第I+1个抽奖点需要做Ci分钟的汽车。Bird希望能在有限的H个小时内获得最好的运气——即抽奖的概率和最大。输入：

第一行为一个整数n，表示抽奖点的个数，1<=n<=200

第二行是两个整数H和T，1<=H<=10，1<=T<=60。

接下来的n行，每行3个整数，分别是Pi，Di，Ci（Cn=0）。1<=Pi<=10000，Di<=Pi，1<=Ci<=600。输出：

一个整数，抽奖概率和的最大值。样例数据input.txtoutput.txt2500120200100103002000样例说明：

首先，bird从1号开始抽奖，花费20分钟，得到概率200，然后坐车到2号，花费10分钟，再花20分钟得到概率300，概率和是500，花费50分钟。此题最初可能想到用搜索，不过如果仔细分析题目会发现其实用贪心就可以解了。虽然中奖的概率会不断变化，但概率只和在该抽奖地点的抽奖次数有关，和抽奖的总次数以及时间无关。所以，我们可以枚举起始S和终点T的抽奖地点，则在路上花费的时间可以求出，那么在这个范围内的抽奖，可以看作bird能瞬间转移，那么我们只需将此范围内的抽奖概率排序，取前若干个，使得花费的时间不超过时限。很容易证明，这种方法是最优的。此题的贪心关键是要先确定一个范围，然后针对具体的范围贪心。贪心法的隐秘性还是比较强的。例题分析（骆驼商队）有N个城市，编号为1……N。在一些城市之间有路可通，有路就有商队。但是在不同的城市之间经商所得的收益不同，在下面的这个N=4的例子中，在城市1和城市2之间进行一次交易可以获得40枚金币，在城市2和3之间交易一次可以获得50枚金币，规定在任意两个城市之间，这样的交易只能进行一次。给出这个大陆的地图和每两个城市之间的贸易值（如果这两个城市之间有路可通的话），你需要指挥你的N支商队进行一次经商，使得这N支商队在这次经商中获得的总收益最大。注意：你的每支商队只能进行一次交易，即它们只能从它们所在的城市到达一个相邻的城市。当然，它们也可以不进行任何交易。分析本题转化成模型就是：在一个无向图中，对于每个点，取一条和它相关联的边（如果这样的边存在的话），使得取出来的所有边的权和最大。首先，如果这个图是不连通的，那么它的各个连通分量之间是没有任何联系的。对这些连通分量中的问题可以分别独立地解决，合并起来就是整个问题的解。所以我们在下面的讨论中假定图是连通的。直观地考虑，如果图中存在度为1的点，那么就把这一点上的唯一的一条边分配给这个点（将某条边“分配”给某个点的含义是：将这条边作为和这一点相关联的边取出来，同时这一点就失效了，因为和它相关联的其他边都不能再取了）。如果不存在这样的点，那么此时有两种情况：一种是边数等于点数，那么这个图就是一个环，这时可以取出图中所有的边；一种是边数大于点数，那么就可以把这个图中权最小的一条边直接删去，因为这条边“显然”不会被取到的。贪心算法（用于连通图）：1、如果图中只有一个点，直接结束算法。2、如果图中存在度为1的点，执行3；否则转4。3、任意找一个度为1的点v，将v上的唯一一条边分配给它。转2。4、如果图中的边数等于点数，执行5；否则转6。5、设图中的点数（也就是边数）为n。任取一条边e1，将它分配给它的两个端点中的任意一个v1；然后将v1上的另一条边e2分配给e2的另一个端点v2；将v2上的另一条边e3分配给e3的另一个端点v3；……如此重复直到将en分配给vn，即图中所有的边都已分配，结束算法。6、将图中权最小的边不分配而直接删去。如果此时图仍然连通，则转2；否则对这个图的两个连通分量分别执行本算法贪心方法的推广贪心与其它算法结合搜索的最优化剪枝（

生日蛋糕）优化动态规划（Peter的快餐店）贪心方法与解题策略最优方法不一定是最好方法想不到最优解法就用较优解法贪心与其它算法结合例题：Peter的快餐店（贪心与动态规划）Peter最近在R市新开了一家快餐店。该快餐店准备推出一种套餐，每套由A个汉堡、B个薯条和C个饮料组成。为了提高产量，Peter引进了N条生产线。所有生产线都可以生产汉堡、薯条和饮料，由于每条生产线一天能工作的时间是有限的、不同的，而汉堡、薯条和饮料的单位生产时间又不同，Peter需要知道，怎样安排才能是一天中生产的套餐量最大。假设一天中汉堡、薯条和饮料的产量均不超过100个，且生产线总数小于等于10。贪心与其它算法结合【分析】用p1、p2、p3分别表示汉堡、薯条和饮料的单位生产时间，t[i]表示第i条生产线每天的生产时间，p[i,j,k]表示用前i条生产线生产j个汉堡、k个薯条的情况下，最多能生产的饮料数，r[i,j,k]表示用第i条生产线生产j个汉堡、k个薯条的情况下，最多能生产的饮料数，则p[i,j,k]=max{p[i-1,j1,k1]+r[i,j-j1,k-k1]}((j-j1)p1+(k-k1)p2<t[i])通过对该算法的时间复杂度分析，最坏的情况下时间复杂度将达到109，是相当费时的。贪心与其它算法结合现在加入贪心方法，用贪心方法作预处理

：首先计算出一天生产套数的上限值：min{100divA,100divB,100divC}接着，用贪心方法计算出这N条生产线可以生产的套数，并与上限比较，大于或等于则输出上限值并退出，否则再调用动态规划。因为贪心方法的代价很低，这里甚至可以使用多次贪心标准不同的贪心方法，取其最大值。在运行动态规划的过程中，也可以每完成一阶段工作便与上限值进行比较，将贪心思想充分融入到动态规划过程中，这样以来，便可望在动态规划完成前提前结束程序。乘车路线编号为1..N的N座城镇用若干道路相连，每条道路上均有两个参数：道路长度(length)和在该条道路上行驶的费用（cost）。BOB准备从城镇1出发到达城镇N，但他目前只有W的钱，为此，你需要帮助他寻找一条从城镇1到城镇N在他能支付的前提下的一条最短路线。分析我们可以在一开始的时候做一下预处理，用MinL[I]表示在不考虑费用的情况下，从城镇I到城镇N的最短路长度。用MinW[I]表示，在不考虑路程的情况下从城镇I到城镇N所需的最少费用（如有多种方案选择路程短的）。这两个数组的值都可以用Dijkstra算法求出来。时间复杂度为O(N*N)，比起后面的搜索算很小了。求出两个数组的值后，我们可以看MinW[1]的值，如果它比W大，显然该问题无解，否则将达到MinW[1]的路程长度作为搜索的下界。

在搜索的时候，设当前在城镇I，已经走的路程长为L，用的费用为W，如果L+MinL[I]>=已找到的最短路长度或是W+MinW[I]>最大可承担费用，再搜索下去显然是没有必要的，此时我们可以剪枝了。贪心方法小结贪心作为一种解题思路，虽然有时无法证明它的正确性，但在无法找到其他算法的时候，不失为一种好方法。并且，贪心与其他算法的结合，可以对其他算法起到优化作用。第四部分分治策略分治思想分治(divide-and-conquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。其三个步骤如下；分解(Divide)：将原问题分成一系列子问题。解决(Conquer)：递归地解各子问题。若子问题足够小，则可直接求解。合并(combine)；将子问题的结果合并成原问题的解。分治的应用解决一类求方程的根的问题解决真假硬币的称量问题基于NLgN算法效率的排序和查找问题分治的应用（求方程的根）例题1：一元三次方程求解有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后4位。提示：记方程f(x)=ax3+bx2+cx+d，若存在2个数x1和x2，且x1<x2，f(x1)*f(x2)<0，则在(x1，x2)之间一定有一个根。样例输入：1-5-420输出：-2.002.005.00分析如果精确到小数点后两位，可用简单的枚举法：将x从-100.00到100.00（步长0.01）逐一枚举，得到20000个f(x)，取其值与0最接近的三个f(x)，对应的x即为答案。而题目已改成精度为小数点后4位，枚举算法时间复杂度将达不到要求。直接使用求根公式，极为复杂。加上本题的提示给我们以启迪：采用二分法逐渐缩小根的范围，从而得到根的某精度的数值。具体方法如下：分析A、当已知区间(a,b)内有一个根时，用二分法求根，若区间(a,b)内有根，则必有f(a)·f(b)<0。重复执行如下的过程：

(1)若a+0.0001>b或f((a+b)/2)=0，则可确定根为(a+b)/2并退出过程；

(2)若f(a)*f((a+b)/2)<0，则由题目给出的定理可知根在区间(a,(a+b)/2)中，故对区间重复该过程；

(3)若f(a)*f((a+b)/2)>0，则必然有f((a+b)/2)*f(b)<0，根在((a+b)/2,b)中，对此区间重复该过程。执行完毕，就可以得到精确到0.0001的根。分析B、求方程的所有三个实根所有的根的范围都在-100至100之间，且根与根之差的绝对值>=1。因此可知：在[-100,-99]、[-99,-98]、……、[99，100]、[100，100]这201个区间内，每个区间内至多只能有一个根。即：除区间[100，100]外，其余区间[a,a+1]，只有当f(a)=0或f(a)·f(a+1)<0时，方程在此区间内才有解。若f(a)=0，解即为a；若f(a)·f(a+1)<0，则可以利用A中所述的二分法迅速出找出解。如此可求出方程的所有的解。分治的应用（求方程的根）例题2：输入m，n，p，a，b，求方程f(x)＝mx+nx-px＝0在[a,b]内的根。m，n，p，a，b均为整数，且a<b；m，n，p都大于等于1。如果有根，则输出，精确到1E-11；如果无方程根，则输出“NO”。【样例】 equation.in equation.out 23412 1.5071265916E+00

2.9103830457E-11分析由于f(x)单调递增函数，对于一个单调递增(或递减)函数，判断在[a,b]范围内是否有解，解是多少。常用的一种方法叫“迭代法”，也就是“二分法”。先判断f(a)·f(b)≤0，如果满足则说明在[a,b]范围内有解，否则无解。如果有解再判断x＝(a+b)/2是不是解，如果是则输出解,结束程序，否则我们采用二分法，将范围缩小到[a,x)或(x,b]，究竟在哪一半区间里有解，则要看是f(a)·f(x)<0还是f(x)·f(b)<0。

对于yx，我们需要用换底公式把它换成exp(xln(y))

分治的应用(分段处理)例题3：取余运算（mod.exe）

输入b，p，k的值，编程计算bpmodk的值。其中的b，p，k*k为长整型数。【输入输出样例】mod.in2109mod.out2^10mod9=7分析

1、用高精度计算比较烦

2、转而用其他方法求解

（1）取模运算的一个规律：a*bmodk=(amodk)*(bmodk)modk

（2）运用规律可以把样例数据分解：b19=b2*9+1=b9b9b，其中的指数9可以继续分解为2×4＋1，4再分解程2×2＋0，2＝1×2＋0，1＝0×1＋1。反过来，我们可以从0出发，通过乘以2再加上1或0推得1，2，4，9，19，然后依次以这些数为指数的自然数除以k的余数。分析（3）不难看出，前面乘以2后要加上的1或0就是该数对应二进制数各位上的数字1或0。如，19＝（10011）2。求解的过程也就是将二进制数还原为十进制数的过程。（4）综上所述，该题可采用分治得思想进行递推求解。找出伪币给你一个装有16枚硬币的袋子。16枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。利用这台仪器，可以知道两组硬币的重量是否相同。分治的应用(称量问题)方法1任意取1枚硬币，与其他硬币进行比较，若发现轻者，这那枚为伪币。最多可能有15次比较。方法2将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为伪币。最多可能有8次比较。方法3分析