算法在信息学奥赛中的应用

算法在信息学奥赛中的应用 (基础篇)

学习过程序设计的人对算法这个词并不陌生，从广义上讲，算法是指为解决一个问题而采用的方法和步骤；从程序计设的角度上讲，算法是指利用程序设计语言的各种语句，为解决特定的问题而构成的各种逻辑组合。我们在编写程序的过程就是在实施某种算法，因此程序设计的实质就是用计算机语言构造解决问题的算法。算法是程序设计的灵魂，一个好的程序必须有一个好的算法，一个没有有效算法的程序就像一个没有灵魂的躯体。

算法具有五个特征：

1、有穷性： 一个算法应包括有限的运算步骤，执行了有穷的操作后将终止运算，不能是个死循环；

2、确切性： 算法的每一步骤必须有确切的定义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，对于相同的输入只能得出相同的输出。如在算法中不允许有“计算8/0”或“将7或8与x相加”之类的运算，因为前者的计算结果是什么不清楚，而后者对于两种可能的运算应做哪一种也不知道。

3、输入：一个算法有0个或多个输入，以描述运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件。如在5个数中找出最小的数，则有5个输入。

4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果，这是算法设计的目的。它们是同输入有着某种特定关系的量。如上述在5个数中找出最小的数，它的出输出为最小的数。如果一个程序没有输出，这个程序就毫无意义了；

5、可行性： 算法中每一步运算应该是可行的。算法原则上能够精确地运行，而且人能用笔和纸做有限次运算后即可完成。

如何来评价一个算法的好坏呢？主要是从两个方面：

一是看算法运行所占用的时间；我们用时间复杂度来衡量，例如：在以下3个程序中，

（1）x:=x+1

（2）for i:=1 to n do

x:=x+1

（3）for i:=1 to n do for j:=1 to n do x:=x+1

含基本操作“x增1”的语句x:=x+1的出现的次数分别为1，n和n2则这三个程序段的时间复杂度分别为O（1），O（n），O（n2），分别称为常量阶、线性阶和平方阶。在算法时间复杂度的表示中，还有可能出现的有：对数阶O(log n)，指数阶O(2n)等。在n很大时，不同数量级的时间复杂度有：O(1)< O(log n)

二是看算法运行时所占用的空间，既空间复杂度。由于当今计算机硬件技术发展很快，程序所能支配的自由空间一般比较充分，所以空间复杂度就不如时间

复杂度那么重要了，有许多问题人们主要是研究其算法的时间复杂度，而很少讨论它的空间耗费。

时间复杂性和空间复杂性在一定条件下是可以相互转化的。在中学生信息学奥赛中，对程序的运行时间作出了严格的限制，如果运行时间超出了限定就会判错，因此在设计算法时首先要考虑的是时间因素，必要时可以以牺牲空间来换取时间，动态规划法就是一种以牺牲空间换取时间的有效算法。对于空间因素，视题目的要求而定，一般可以不作太多的考虑。

我们通过一个简单的数值计算问题，来比较两个不同算法的效率（在这里只比较时间复杂度）。

例：求N！所产生的数后面有多少个0（中间的0不计）。

算法一：从1乘到n，每乘一个数判断一次，若后面有0则去掉后面的0，并记下0的个数。为了不超出数的表示范围，去掉与生成0无关的数，只保留有效位数，当乘完n次后就得到0的个数。（pascal程序如下） var i,t,n,sum:longint; begin

t:=0; sum:=1; readln(n);

for i:=1 to n do begin

sum:=sum*i;

while sum mod 10=0 do begin

sum:=sum div 10;

inc(t);{计数器增加1} end;

sum:=sum mod 1000;{舍去与生成0无关的数} end;

writeln(t:6); end.

算法二：此题中生成O的个数只与含5的个数有关，n！的分解数中含5的个数就等于末尾O的个数，因此问题转化为直接求n！的分解数中含5的个数。 var t,n:integer; begin

readln(n); t:=0; repeat

n:=n div 5 ;

inc(t,n); {计数器增加n} until n<5; writeln(t:6); end.

分析对比两种算法就不难看出，它们的时间复杂度分别为O（N）、O（logN）,算法二的执行时间远远小于算法一的执行时间。

在信息学奥赛中，其主要任务就是设计一个有效的算法，去求解所给出的问题。如果仅仅学会一种程序设计语言，而没学过算法的选手在比赛中是不会取得好的成绩的，选手水平的高低在于能否设计出好的算法。

下面，我们根据全国分区联赛大纲的要求，一起来探讨信息学奥赛中的基本算法。

信息学奥赛中的基本算法(枚举法)

枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。

采用枚举算法解题的基本思路：

（1） 确定枚举对象、枚举范围和判定条件； （2） 一一枚举可能的解，验证是否是问题的解

下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定，这三个方面来探讨如何用枚举法解题。

例1：百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，大鸡三块钱一只，小鸡一块钱三只，不大不小的鸡两块钱一只。现在，请你编一程序，帮他计划一下，怎么样买法，才能刚好用一百块钱买一百只鸡？

算法分析：此题很显然是用枚举法，我们以三种鸡的个数为枚举对象（分别设为x,y,z）,以三种鸡的总数（x+y+z）和买鸡用去的钱的总数(x*3+y*2+z)为判定条件，穷举各种鸡的个数。

下面是解这个百鸡问题的程序 var x,y,z:integer; begin

for x:=0 to 100 do for y:=0 to 100 do

for z:=0 to 100 do{枚举所有可能的解}

if (x+y+z=100)and(x*3+y*2+z div 3=100)and(z mod 3=0)then

writeln('x=',x,'y=',y,'z=',z); {验证可能的解，并输出符合题目要求的解} end.

上面的条件还有优化的空间，三种鸡的和是固定的，我们只要枚举二种鸡（x,y），第三种鸡就可以根据约束条件求得（z=100-x-y），这样就缩小了枚举范围，请看下面的程序： var x,y,z:integer; begin

for x:=0 to 100 do

for y:=0 to 100-x do begin

z:=100-x-y; if (x*3+y*2+z div writeln('x=',x,'y=',y,'z=',z);

end; end.

3=100)and(z mod 3=0)then

未经优化的程序循环了1013 次，时间复杂度为O(n3)；优化后的程序只循环了（102*101/2）次 ，时间复杂度为O(n2)。从上面的对比可以看出，对于枚举算法，加强约束条件，缩小枚举的范围，是程序优化的主要考虑方向。

在枚举算法中，枚举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的枚举对象可以获得更高的效率。如下例：

例2、将1,2...9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,试求出所有满足条件的三个三位数.

例如:三个三位数192,384,576满足以上条件.(NOIP1998pj) 算法分析：这是1998年全国分区联赛普及组试题（简称NOIP1998pj，以下同）。此题数据规模不大，可以进行枚举，如果我们不加思地以每一个数位为枚举对象，一位一位地去枚举：

for a:=1 to 9 do for b:=1 to 9 do

???

for i:=1 to 9 do

这样下去，枚举次数就有9９次，如果我们分别设三个数为x,2x,3x，以x为枚举对象，穷举的范围就减少为９３，在细节上再进一步优化，枚举范围就更少了。程序如下： var

t,x:integer; s,st:string; c:char; begin

for x:=123 to 321 do{枚举所有可能的解} begin t:=0;

str(x,st);{把整数x转化为字符串，存放在st中} str(x*2,s); st:=st+s; str(x*3,s); st:=st+s;

for c:='1' to '9' do{枚举9个字符，判断是否都在st中}

if pos(c,st)<>0 then inc(t) else break;{如果不在st中，则退出循环}

if t=9 then writeln(x,' ',x*2,' ',x*3); end; end.

在枚举法解题中，判定条件的确定也是很重要的，如果约束条件不对或者不全面，就穷举不出正确的结果， 我们再看看下面的例子。

例３ 一元三次方程求解(noip2001tg)

问题描述 有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。

要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。

提示：记方程f(x)=0，若存在2个数x1和x2，且x1

样例

输入：1 -5 -4 20 输出：-2.00 2.00 5.00

算法分析：由题目的提示很符合二分法求解的原理，所以此题可以用二分法。用二分法解题相对于枚举法来说很要复杂很多。此题是否能用枚举法求解呢？再分析一下题目，根的范围在-100到100之间，结果只要保留两位小数，我们不妨将根的值域扩大100倍（-10000<=x<=10000），再以根为枚举对象，枚举范围是-10000到10000，用原方程式进行一一验证，找出方程的解。

有的同学在比赛中是这样做 var

k:integer;

a,b,c,d,x :real; begin

read(a,b,c,d);

for k:=-10000 to 10000 do begin

x:=k/100;

if a*x*x*x+b*x*x+c*x+d=0 then write(x:0:2,' '); end; end.

用这种方法，很快就可以把程序编出来，再将样例数据代入测试也是对的，等成绩下来才发现这题没有全对，只得了一半的分。

这种解法为什么是错的呢？错在哪里？前面的分析好象也没错啊，难道这题不能用枚举法做吗？ 看到这里大家可能有点迷惑了。

在上面的解法中，枚举范围和枚举对象都没有错，而是在验证枚举结果时，判定条件用错了。因为要保留二位小数，所以求出来的解不一定是方程的精确根，

再代入ax3+bx2+cx+d中，所得的结果也就不一定等于0，因此用原方程ax3+bx2+cx+d=0作为判断条件是不准确的。

我们换一个角度来思考问题，设f(x)=ax3+bx2+cx+d，若x为方程的根，则根据提示可知，必有f(x-0.005)*(x+0.005)<0，如果我们以此为枚举判定条件，问题就逆刃而解。另外，如果f(x-0.005)=0，哪么就说明x-0.005是方程的根，这时根据四舍5入，方程的根也为x。所以我们用(f(x-0.005)*f(x+0.005)<0) 和 (f(x-0.005)=0)作为判定条件。为了程序设计的方便，我们设计一个函数f(x)计算ax3+bx2+cx+d的值，程序如下： {$N+} var

k:integer;

a,b,c,d,x:extended;

function f(x:extended):extended; {计算ax3+bx2+cx+d的值} begin

f:=((a*x+b)*x+c)*x+d; end; begin

read(a,b,c,d);

for k:=-10000 to 10000 do begin

x:=k/100;

if (f(x-0.005)*f(x+0.005)<0) or (f(x-0.005)=0) then write(x:0:2,' '); {若x两端的函数值异号或x-0.005刚好是方程的根，则确定x为方程的根} end; end.

用枚举法解题的最大的缺点是运算量比较大，解题效率不高，如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。但枚举算法的思路简单，程序编写和调试方便，比赛时也容易想到，在竞赛中，时间是有限的，我们竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么我们最好是采用枚举法，而不需太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。

信息学奥赛中的基本算法(回溯法)

如果上期的“百钱买百鸡”中鸡的种类数是变化的，用枚举法就无能为力了，这里介绍另一种算法——回溯法。

回溯法是一种既带有系统性又带有跳跃性的搜索法，它的基本思想是：在搜索过程中，当探索到某一步时，发现原先的选择达不到目标，就退回到上一步重新选择。它主要用来解决一些要经过许多步骤才能完成的，而每个步骤都有若干

种可能的分支，为了完成这一过程，需要遵守某些规则，但这些规则又无法用数学公式来描述的一类问题。下面通过实例来了解回溯法的思想及其在计算机上实现的基本方法。

例1、从N个自然数(1,2,…,n)中选出r个数的所有组合。

算法分析：设这r个数为a1,a2,?ar,把它们从大到小排列，则满足： （1） a1>a2>?>ar;

（2） 其中第i位数(1<=i<=r)满足ai>r-i;

我们按以上原则先确定第一个数，再逐位生成所有的r个数，如果当前数符合要求，则添加下一个数;否则返回到上一个数，改变上一个数的值再判断是否符合要求，如果符合要求，则继续添加下一个数，否则返回到上一个数，改变上一个数的值??按此规则不断循环搜索，直到找出r个数的组合，这种求解方法就是回溯法。

如果按以上方法生成了第i位数ai，下一步的的处理为：

（1） 若ai>r-i且i=r，则输出这r个数并改变ai的值:ai=ai-1; （2） 若ai>r-i且i≠r，则继续生成下一位ai+1=ai-1;

（3） 若ai<=r-i，则回溯到上一位，改变上一位数的值:ai-1=ai-1-1; 算法实现步骤：

第一步：输入n,r的值，并初始化； i:=1;a[1]:=n; 第二步：若a[1]>r-1则重复：

若a[i]>r-i，①若i=r，则输出解，并且a[i]:=a[i]-1;

②若i<>r，则继续生成下一位：a[i+1]:=a[i]-1; i:=i+1;

若 a[i]<=r-i，则回溯：i:=i-1; a[i]:=a[i]-1; 第三步：结束； 程序实现

var n,r,i,j:integer;

a:array[1..10] of integer; begin

readln(n,r);i:=1;a[1]:=n; repeat

if a[i]>r-i then {符合条件 } if i=r then {输出}

begin

for j:=1 to r do write(a[j]:3); writeln;

a[i]:=a[i]-1; end

else {继续搜索}

begin a[i+1]:=a[i]-1; i:=i+1;end

else{回溯}

begin i:=i-1; a[i]:=a[i]-1;end; until a[1]=r-1; end.

下面我们再通过另一个例子看看回溯在信息学奥赛中的应用。 例2 数的划分（noip2001tg）

问题描述 整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。 例如：n=7，k=3，下面三种分法被认为是相同的。

1，1，5; 1，5，1; 5，1，1; 问有多少种不同的分法。

输入：n，k (6

输入： 7 3

输出：4 {四种分法为：1,1,5; 1,2,4; 1,3,3; 2,2,3;}

算法分析：此题可以用回溯法求解，设自然数n拆分为a1,a2,…,ak,必须满足以下两个条件：

（1） n=a1+a2+…+ak ；

（2） a1<=a2<=…<=ak (避免重复计算)；

现假设己求得的拆分数为a1,a2,…ai,且都满足以上两个条件,设sum=n-a1-a2-…-ai,我们根据不同的情形进行处理：

（1） 如果i=k,则得到一个解，则计数器t加1，并回溯到上一步，改变ai-1的值； （2） 如果i=ai,则添加下一个元素ai+1；

（3） 如果i第一步：输入自然数n,k并初始化；t:=0; i:=1;a[i]:=1; sum:=n-1; nk:=n div k;

第二步：如果a[1]<=nk 重复：

若i=k，搜索到一个解，计数器t=t+1;并回溯； 否则：①若sum>=a[i]则继续搜索；

②若sum

搜索时，inc(i);a[i]:=a[i-1];sum:=sum-a[i]; 回溯时，dec(i); inc(a[i]); sum:=sum+a[i+1]-1; 第三步：输出。 程序如下： var

n,nk,sum,i,k:integer; t:longint;

a:array[1..6]of integer; begin

readln(n,k); nk:=n div k;

t:=0; i:=1;a[i]:=1; sum:=n-1;{初始化} repeat

if i=k then{判断是否搜索到底}

begin inc(t); dec(i);inc(a[i]); sum:=sum+a[i+1]-1; end {回溯} else begin

if sum>=a[i] then {判断是否回溯}

begin inc(i);a[i]:=a[i-1];sum:=sum-a[i];end{继续搜}

else begin dec(i); inc(a[i]); sum:=sum+a[i+1]-1; end;{回溯} end;

until a[1]>nk; writeln(t); end.

回溯法是通过尝试和纠正错误来寻找答案，是一种通用解题法，在NOIP中有许多涉及搜索问题的题目都可以用回溯法来求解。

信息学奥赛中的基本算法(递归算法)

递归算法的定义：如果一个对象的描述中包含它本身，我们就称这个对象是递归的，这种用递归来描述的算法称为递归算法。

我们先来看看大家熟知的一个的故事：

从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说??

上面的故事本身是递归的，用递归算法描述： procedure bonze-tell-story； begin

if 讲话被打断 then 故事结束 else begin

从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事； bonze-tell-story； end end;

从上面的递归事例不难看出，递归算法存在的两个必要条件： （1） 必须有递归的终止条件； （2） 过程的描述中包含它本身；

在设计递归算法中，如何将一个问题转化为递归的问题，是初学者面临的难题，下面我们通过分析汉诺塔问题，看看如何用递归算法来求解问题；

例1：汉诺塔问题，如下图，有A、B、C三根柱子。A柱子上按从小到大的顺序堆放了N个盘子，现在要把全部盘子从A柱移动到C柱，移动过程中可以借助B柱。移动时有如下要求：

（1） 一次只能移动一个盘子；

（2） 不允许把大盘放在小盘上边； （3） 盘子只能放在三根柱子上；

算法分析：当盘子比较多的时，问题比较复杂，所以我们先分析简单的情况： 如果只有一个盘子，只需一步，直接把它从A柱移动到C柱； 如果是二个盘子，共需要移动3步: （1） 把A柱上的小盘子移动到B柱; （2） 把A柱上的大盘子移动到C柱； （3） 把B柱上的大盘子移动到C柱；

如果N比较大时，需要很多步才能完成，我们先考虑是否能把复杂的移动过程转化为简单的移动过程，如果要把A柱上最大的盘子移动到C柱上去，必须先把上面的N-1个盘子从A柱移动到B柱上暂存，按这种思路，就可以把N个盘子的移动过程分作3大步：

（1） 把A柱上面的N-1个盘子移动到B柱； （2） 把A柱上剩下的一个盘子移动到C柱； （3） 把B柱上面的N-1个盘子移动到C柱；

其中N-1个盘子的移动过程又可按同样的方法分为三大步，这样就把移动过程转化为一个递归的过程，直到最后只剩下一个盘子，按照移动一个盘子的方法移动，递归结束。

递归过程：

procedure Hanoi(N,A,B,C:integer;)；{以B柱为中转柱将N个盘子从A柱移动到C柱} begin

if N=1 then write(A,’->’,C){把盘子直接从A移动到C} else begin

Hanoi(N-1,A,C,B)；{ 以C柱为中转柱将N-1个盘子从A柱移动到B柱} write(A,’->’,C)；{把剩下的一个盘子从A移动到C}

Hanoi(N-1,B,A,C)； { 以A柱为中转柱将N-1个盘子从B柱移动到C柱} end; end;

从上面的例子我们可以看出，在使用递归算法时，首先弄清楚简单情况下的解法，然后弄清楚如何把复杂情况归纳为更简单的情况。

在信息学奥赛中有的问题的结构或所处理的数据本身是递归定义的，这样的问题非常适合用递归算法来求解，对于这类问题，我们把它分解为具有相同性质的若干个子问题，如果子问题解决了，原问题也就解决了。

例2求先序排列 (NOIP2001pj)

[问题描述]给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。

（4） 若“4”第四个输出，与情况（1）相同，总数为f(3); 所以有：f(4)=f(3)+f(1)*f(2)+f(2)*f(1)+f(3); 若设0个数通过栈后的排列总数为：f(0)=1；

上式可变为：f(4)=f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0); 再进一步推导，不难推出递推式：

f(n)=f(0)*f(n-1)+f(1)*f(n-2)+?+f(n-1)*f(0); 即f(n)=

0?i?n?1?f(i)*f(n?i?1) (n>=1)

初始值：f(0)=1;

有了以上递推式，就很容易用递推法写出程序。

var

a:array[0..18]of longint; n,i,j:integer; begin

readln(n);

fillchar(a,sizeof(a),0); a[0]:=1;

for i:=1 to n do

for j:=0 to i-1 do a[i]:=a[i]+a[j]*a[i-j-1]; writeln(a[n]); end.

递推算法最主要的优点是算法结构简单，程序易于实现，难点是从问题的分析中找出解决问题的递推关系式。对于以上两个例子，如果在比赛中找不出递推关系式，也可以用回溯法求解。

算法在信息学奥赛中的应用 (分治法)

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

分治法解题的一般步骤：

（1）分解，将要解决的问题划分成若干规模较小的同类问题； （2）求解，当子问题划分得足够小时，用较简单的方法解决；

（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。 例1、 比赛安排(noip1996)

设有2^n(n<=6)个球队进行单循环比赛,计划在2^n-1天内完成,每个队每天进行一场比赛。设计一个比赛的安排,使在2^n-1天内每个队都与不同的对手比赛。例如n=2时的比赛安排为:

队 1 2 3 4

比赛 1-2 3-4 第一天

1-3 2-4 第二天 1-4 2-3 第三天

算法分析：此题很难直接给出结果，我们先将问题进行分解，设m=2^n，将规模减半，如果n=3(即m=8),8个球队的比赛，减半后变成4个球队的比赛（m=4），4个球队的比赛的安排方式还不是很明显，再减半到两个球队的比赛(m=2)，两个球队的比赛安排方式很简单，只要让两个球队直接进行一场比赛即可： 1 2 2 1 分析两个球队的比赛的情况不难发现，这是一个对称的方阵，我们把这个方阵分成4部分（即左上，右上，左下，右下），右上部分可由左上部分加1（即加m/2）得到，而右上与左下部分、左上与右下部分别相等。因此我们也可以把这个方阵看作是由M=1的方阵所成生的，同理可得M=4的方阵： 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 同理可由M=4方阵生成M=8的方阵： 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 6 7 8 1 2 3 4 5 8 7 2 1 4 3 8 5 6 3 4 1 2 7 6 5 4 3 2 1 这样就构成了整个比赛的安排表。

在算法设计中，用数组a记录2^n个球队的循环比赛表，整个循环比赛表从最初的1*1方阵按上述规则生成2*2的方阵，再生成4*4的方阵，??直到生成出整个循环比赛表为止。变量h表示当前方阵的大小,也就是要生成的下一个方阵的一半。 源程序： var

i,j,h,m,n:integer;

a:array[1..32,1..32]of integer; begin

readln(n);

m:=1;a[1,1]:=1;h:=1; for i:=1 to n do m:=m*2;

repeat

for i:=1 to h do

for j:=1 to h do begin

a[i,j+h]:=a[i,j]+h;{构造右上角方阵} a[i+h,j]:=a[i,j+h];{构造左下角方阵} a[i+h,j+h]:=a[i,j];{构造右下角方阵} end; h:=h*2; until h=m;

for i:=1 to m do begin

for j:=1 to m do write(a[i,j]:4); writeln; end; end.

在分治算法中，若将原问题分解成两个较小的子问题，我们称之为二分法，由于二分法划分简单，所以使用非常广泛。使用二分法与使用枚举法求解问题相比较，时间复杂度由O（N）降到O（log2N），在很多实际问题中，我们可以通过使用二分法，达到提高算法效率的目的，如下面的例子。

例2 一元三次方程求解（noip2001tg）

题目大意：给出一个一元三次方程f(x)=ax3+bx2+cx+d=0 ,求它的三个根。所有的根都在区间[-100，100]中，并保证方程有三个实根，且它们之间的差不小于1。

算法分析：在讲解枚举法时，我们讨论了如何用枚举法求解此题，但如果求解的精度进一步提高，使用枚举法就无能为力了，在此我们再一次讨论如何用二分法求解此题。

由题意知（i,i+1）中若有根，则只有一个根，我们枚举根的值域中的每一个整数x(-100≤x≤100),设定搜索区间[x1，x2]，其中x1=x，x2=x+1。若： ⑴f(x1)=0，则确定x1为f(x)的根；

⑵f(x1)*f(x2)<0，则确定根x在区间[x1，x2]内。

⑶f(x1)*f(x2)>0，则确定根x不在区间[x1，x2]内，设定[x2，x2+1]为下一个搜索区间；

若确定根x在区间[x1，x2]内，采用二分法，将区间[x1，x2]分成左右两个子区间：左子区间[x1，x]和右子区间[x，x2]（其中x=（x1+x2）/2）。如果f(x1)*f(x)≤0，则确定根在左区间[x1，x]内，将x设为该区间的右界值（x2=x），继续对左区间进行对分；否则确定根在右区间[x，x2]内，将x设为该区间的左界值（x1=x），继续对右区间进行对分；

上述对分过程一直进行到区间的间距满足精度要求为止（即x2-x1<0.005）。此时确定x1为f(x)的根。

源程序： {$N+}

var

x:integer;

a,b,c,d,x1,x2,xx:extended;

function f(x:extended):extended; begin

f:=((a*x+b)*x+c)*x+d; end; begin

read(a,b,c,d);

for x:=-100 to 100 do begin

x1:=x;x2:=x+1;

if f(x1)=0 then write(x1:0:2,' ') else if f(x1)*f(x2)<0 then begin

while x2-x1>=0.005 do begin

xx:=(x1+x2)/2;

if f(x1)*f(xx)<=0 then x2:=xx else x1:=xx; end;{while}

write(x1:0:2,' '); end; {then} end;{for} end.

信息学奥赛中的基本算法(贪心法)

在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。

从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。

我们看看下面的例子

例1 均分纸牌（NOIP2002tg）

[问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ① 9 ② 8 ③ 17 ④ 6 移动3次可达到目的：

从 ③ 取 4 张牌放到 ④ （9 8 13 10） -> 从 ③ 取 3 张牌放到 ②（9 11 10 10）-> 从 ② 取 1 张牌放到①（10 10 10 10）。 [输 入]：键盘输入文件名。

文件格式：N（N 堆纸牌，1 <= N <= 100）

A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输 出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in：

4

9 8 17 6 屏慕显示：3

算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。

我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0

（1） 若a[i]>v，则将a[i]-v张纸牌从第I堆移动到第I+1堆； （2） 若a[i]

为了设计的方便，我们把这两种情况统一看作是将a[I]-v张牌从第I堆移动到第I+1堆；移动后有：a[I]:=v；a[I+1]:=a[I+1]+a[I]-v；

在从第i+1堆中取出纸牌补充第i堆的过程中，可能会出现第i+1堆的纸牌数小于零(a[i+1]+a[i]-v<0 )的情况。

如n=3，三堆纸牌数为（1，2，27）这时v=10，为了使第一堆数为10，要从第二堆移9张纸牌到第一堆，而第二堆只有2张纸牌可移，这是不是意味着刚才使用的贪心法是错误的呢？

我们继续按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有10张纸牌，第二堆剩下-7张纸牌，再从第三堆移动17张到第二堆，刚好三堆纸牌数都是10，最后结果是对的，从第二堆移出的牌都可以从第三堆得到。我们在移动过程中，只是改变了移动的顺序，而移动的次数不变，因此此题使用贪心法是可行的。

源程序： var

i,n,s:integer;v:longint; a:array[1..100]of longint; f:text;fil:string; begin

readln(fil);

assign(f,fil);reset(f); readln(f,n);v:=0;

for i:=1 to n do begin

read(f,a[i]); inc(v,a[i]); end;

v:=v div n; {每堆牌的平均数} for i:=1 to n-1 do

if a[i]<>v then {贪心选择} begin

inc(s);{移牌步数计数}

a[i+1]:=a[i+1]+a[i]-v;{使第i堆牌数为v} end;{then} writeln(s); end.

利用贪心算法解题，需要解决两个问题：

一是问题是否适合用贪心法求解。我们看一个找币的例子,如果一个货币系统有3种币值,面值分别为一角、五分和一分，求最小找币数时，可以用贪心法求解；如果将这三种币值改为一角一分、五分和一分，就不能使用贪心法求解。用贪心法解题很方便，但它的适用范围很小，判断一个问题是否适合用贪心法求解，目前还没有一个通用的方法，在信息学竞赛中，需要凭个人的经验来判断何时该使用贪心算法。

二是确定了可以用贪心算法之后，如何选择一个贪心标准，才能保证得到问题的最优解。在选择贪心标准时，我们要对所选的贪心标准进行验证才能使用，不要被表面上看似正确的贪心标准所迷惑，如下面的列子。

例2 （NOIP1998tg）设有n个正整数，将他们连接成一排，组成一个最大的多位整数。例如:n=3时，3个整数13,312,343,连成的最大整数为:34331213

又如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613 输入：N

N个数

输出:连接成的多位数

算法分析：此题很容易想到使用贪心法，在考试时有很多同学把整数按从大到小的顺序连接起来，测试题目的例子也都符合，但最后测试的结果却不全对。按这种贪心标准，我们很容易找到反例：12，121 应该组成12121而非12112,那么是不是相互包含的时候就从小到大呢？也不一定，如：12，123 就是12312而

非12112,这样情况就有很多种了。是不是此题不能用贪心法呢？

其实此题是可以用贪心法来求解，只是刚才的贪心标准不对，正确的贪心标准是：先把整数化成字符串，然后再比较a+b和b+a，如果a+b>b+a，就把a排在b的前面，反之则把a排在b的后面。 源程序： var

s:array[1..20] of string; t:string;i,j,k,n:longint; begin

readln(n);

for i:=1 to n do begin read(k);

str(k,s[i]); end;

for i:=1 to n-1 do for j:=i+1 to n do

if s[i]+s[j]

for i:=1 to n do write(s[i]); end.

贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。

算法在信息学奥赛中的应用（搜索法一）

在这里介绍两种基本的搜索算法：深度优先搜索和广度优先搜索法，以树的搜索为例，深度优先搜索法是优先扩展尚未扩展的且具有最大深度的结点；广度优先搜索法是在扩展完第K层的结点以后才扩展K+1层的结点。

深度优先搜索法与前面讲的回溯法差不多，主要的区别是回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树，搜索树起记录解路径和状态判重的作用。为了减少存储空间，在深度优先搜索中，用标志的方法

记录访问过的状态，这种处理方法使得深度优先搜索法与回溯法没什么区别了。在回溯法中，我们己分析了非递归的实现过程，在这里就只讨论深度优先的递归实现方法。

深度优先搜索的递归实现过程： procedure dfs(i); for i:=1 to r do

if 子结点mr符合条件then 产生的子结点mr入栈； if 子结点 mr 是目标结点 then 输出

else dfs(i+1);

栈顶元素出栈（即删去mr）; endif; endfor;

在讲解递推法时，我们讨论了用递推法解骑土游历问题，在这里我们再看看如何用深度优先搜索法求解此题。

例1骑士游历:设有一个n*m的棋盘，在棋盘上任一点有一个中国象棋马,马走的规则为:1.马走日字 2.马只能向右走。当N,M 输入之后,找出一条从左下角到右上角的路径。例如:输入 N=4,M=4，输出:路径的格式:(1,1)->(2,3)->(4,4)，若不存在路径,则输出\算法分析：我们以4×4的棋盘为例进行分析，用树形结构表示马走的所有过程（如下图），求从起点到终点的路径,实际上就是从根结点开始深度优先搜索这棵树。

马从（1，1）开始，按深度优先搜索法，走一步到达（2，3），判断是否到达终点，若没有，则继续往前走，再走一步到达（4，4），然后判断是否到达终点，若到达则退出，搜索过程结束。为了减少搜索次数，在马走的过程中，判断下一步所走的位置是否在棋盘上，如果不在棋盘上，则另选一条路径再走。 程序如下：

const

dx:array[1..4]of integer=(2,2,1,1); dy:array[1..4]of integer=(1,-1,2,-2); type

map=record

x,y:integer; end; var

i,n,m:integer;

a:array[0..50]of map; procedure dfs(i:integer); var j:integer; begin

for j:=1 to 4 do

if (a[i-1].x+dx[j]>0)and(a[i-1].x+dx[j]<=n)

and(a[i-1].y+dy[j]>0)and(a[i-1].y+dy[j]<=n) then{判断是否在棋盘上} begin

a[i].x:=a[i-1].x+dx[j];

a[i].y:=a[i-1].y+dy[j];{入栈} if (a[i].x=n)and(a[i].y=m)then begin

write('(',1,',',1,')');

for j:=2 to i do write('->(',a[j].x,',',a[j].y,')'); halt;{输出结果并退出程序} end;

dfs(i+1);{搜索下一步}

a[i].x:=0;a[i].y:=0;{出栈} end; end; begin

a[1].x:=1;a[1].y:=1; readln(n,m); dfs(2); writeln('no'); end.

从上面的例子我们可以看出，深度优先搜索算法有两个特点：

1、己产生的结点按深度排序，深度大的结点先得到扩展，即先产生它的子结点。 2、深度大的结点是后产生的，但先得到扩展，即“后产生先扩展”，与栈的工作原理相同，因此用堆栈作为该算法的主要数据结构，存储产生的结点。 对于不同的问题，深度优先搜索算法基本上是一样的，但在具体处理方法和

编程技巧上又都不相同，甚至会有很大的差别。我们再看看另一个例子。 题二 选数（存盘名：NOIP2002pj）

[问题描述]:已知 n 个整数 x1,x2,?,xn，以及一个整数 k(k＜n)。从n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。现在，要求你计算出和为素数共有多少种。例如上例，只有一种的和为素数：3＋7＋19＝29。 [输入]：键盘输入，格式为： n , k (1<=n<=20，k＜n)

x1,x2，?,xn （1<=xi<=5000000） [输出]：屏幕输出，格式为：

一个整数（满足条件的种数）。 [输入输出样例]: 输入：4 3

3 7 12 19 输出：1

算法分析：本题是求从n个数中选k个数的组合，并使其和为素数。求解此题时，先用深度优先搜索法生成k个数的组合，再判断k个数的和是否为素数，若为素数则总数加1。

在程序实现过程中，用数组a存放输入的n个数，用s表示k个数的和，ans表示和为素数的个数。为了避免不必要的搜索，程序对搜索过程进行了优化，限制搜索范围，在搜索过程dfs(i,m)中，参数m为第i个数的上限，下限为n-k+i。 源程序： var

n,k,i: byte;

ans,s:longint;

a: array[1 .. 20] of Longint;

procedure prime(s:longint);{判断K个数的和是否为素数} var

i:integer; begin i:=2;

while (sqr(i)<=s)and(s mod i<>0) do inc(i); if sqr(i)>s then inc(ans){若为素数则总数加1} end;

procedure dfs(i,m:byte);{搜索第i个数， } var

j:byte;{j表示第i个数的位置 begin

for j:=m to n-k+i do{枚举第i个数} begin

inc(s,a[j]);{入栈}

if i=k then prime(s)

else dfs(i+1,j+1);{继续搜第i+1个数} dec(s,a[j]){出栈} end end; begin

readln(n,k);

for i:=1 to n do read(a[i]);

ans:=0; s:=0; dfs(1,1);

writeln(ans); end.

从上面的两个例子我们可以看出，用递归实现深度优先搜索比非递归更加方便。

在使用深度搜索法解题时，搜索的效率并不高，所以要重视对算法的优化，尽可能的减少搜索范围，提高程序的速度。

在下一篇中将继续介绍另一种搜索方法——广度优先搜索法。

算法在信息学奥赛中的应用（搜索法二） 在深度优先搜索算法中，深度越大的结点越先得到扩展，若把它改为深度越小的结点越先得到扩展，就是广度优先搜索法。

广度优先搜索基本算法： program bfs;

初始化；建立队列data;

设队列首指针closed:=0;队列尾指针open:=1; repeat

closed 增1，取出closed所指结点进行扩展； for i:=1 to r do begin if 子结点符合条件then begin

open增1，并把新结点存入数据库队尾；

if新结点与原有结点有重复 then 删于该结点(open减1) else if 新结点即目标 then 输出并退出 ;

end{if}; end{for};

until closed>=open;{队列为空}

使用广度优先搜索时，离根结点最近的结点先扩展，所以广度优先搜索法比较适合求步数最少的解，由于深度优先使用了标志法，使得存储空间大大减少，而广度优先要保留所有搜索过的节点，随着搜索程度的加深，所需的存储空间成指数增加。因此在必要时我们采用双向搜索来减少搜索空间和存储空间，如下面的例子。

例 字串变换（NOIP2002tg）

[问题描述]:已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）: A1$ -> B1$ A2$ -> B2$ 规则的含义为：在 A$中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ ?。例如：A$＝'abcd' B$＝'xyz' 变换规则为：‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’ 则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：‘abcd’->‘xud’->‘xy’->‘xyz’ 共进行了三次变换，使得 A$ 变换为B$。 [输入]:键盘输人文件名。文件格式如下： A$ B$

A1$ B1$ \\

A2$ B2$ |-> 变换规则 ... ... /

所有字符串长度的上限为 20。

[输出]:输出至屏幕。格式如下： 若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出\[输入输出样例] b.in: abcd xyz abc xu ud y y yz 屏幕显示：3

算法分析：此题是求变换的最少步数，很显然可以使用广度优先搜索法，如果直接从初状态搜到目标状态，最坏情况下存储的结点数超过6的10次方幂，搜索空间过大，因此我们考虑使双向搜索，同时从初始状态和目标状态向中间状态搜索，当相遇时搜索结束。采用双向搜索，存储的结点数还有可能超限，我们在前向搜索队列中存储5步内变换的结点，在后向搜索队列中，由于第5步产生的结点只是用来与前向队列中的结点比较，所以可以不存储在队列中，后向搜索队列只需存储4步内的结点，这样就解决了存储空间问题。

为了使用方便，在程序设计中用一个数组a[1..max]存储两个队列，前向搜索队列为a[1..mid]，后向搜索队列为a[mid..max]，用st存储搜索方向，st=0表示前向搜索，st=1表示后向搜索，用op[st]和cl[st]分别表示队列尾指针和首指针，用be表示队列起始位置，循环产生每一个结点，若在10内无解退出循环，若在10内找到解则输出解并退出程序。

源程序：

const mid=12000;max=16000; type

node=record s:string;x:byte;end; var

i,mark:integer;

a:array [1..max]of ^node;

x:array[0..6,0..1]of string[20]; d,fil:string;

op,cl:array [0..1] of integer; procedure Init;{读取数据，初始化} var f:text;t:string; begin

readln(fil);

assign(f,fil);reset(f);i:=0;

while not eof(f) do begin readln(f,t);

x[i,0]:=copy(t,1,pos(' ',t)-1);

x[i,1]:=copy(t,pos(' ',t)+1,length(t)); inc(i); end;{while}

mark:=i-1;close(f); end;

{判断是否到达目标状态}

procedure bool(be,st:integer); begin

for i:=mid-be+1 to cl[1-st] do

if a[cl[st]]^.s=a[i]^.s then begin writeln(a[cl[st]]^.x+a[i]^.x); halt; end;{if} end;

{判断节点是否与前面的结点重复} procedure check(be,st:integer); begin

for i:=be+1 to cl[st]-1 do

if a[i]^.s=a[cl[st]]^.s then begin dec(cl[st]);exit; end; bool(be,st); end;

{扩展产生新节点}

procedure expand(be,st:integer); var i,j,k,lx,ld:integer; begin

inc(op[st]);d:=a[op[st]]^.s; k:=a[op[st]]^.x;ld:=length(d); for i:=1 to mark do begin lx:=length(x[i,st]); for j:=1 to ld do begin

if (copy(d,j,lx)=x[i,st]) then begin if (st<>1)or(k<>4)then begin inc(cl[st]); new(a[cl[st]]); end;{if}

a[cl[st]]^.s:= copy(d,1,j-1)+ x[i,1-st]+ copy(d,j+lx,ld); a[cl[st]]^.x:=k+1;

check(be,st);{检查是否重复} end;{if} end;{for} end;{for} end;

procedure bfs;

var be,k,st:integer; Begin

for st:=0 to 1 do begin

if st=0 then be:=0 else be:=mid; op[st]:=be+0;cl[st]:=be+1; new(a[cl[st]]);

a[cl[st]]^.s:=x[0,st]; a[cl[st]]^.x:=0; end;{for} repeat

if (op[0]=cl[0])or(a[cl[0]]^.x>5)or(op[1]>=cl[1])or (a[cl[1]]^.x>5); End; BEGIN

init;bfs;writeln('NO ANSWER!') END.

两种搜索算法的比较： 搜索方式 扩展方式 深度优先 后产生先扩展 广度优先 先产生先扩展 数据结构 适合求解的问题 栈 队列 可行解或所有解 最优解 在选择搜索方式时，并不是完全遵循以上原则，具体还是要根据题目的要求而定。在求最优解时，如果搜索的深度不大，我们也可以考虑使用深度优先搜索；在求解可行解时，如果搜索的深度没有限制，或者搜索的代价与搜索的深度成正比,我们也应该使用广度优先搜索。

算法在信息学奥赛中的应用（动态规划法）

在学习动态规划法之前，我们先来了解动态规划的几个概念

1、 阶段：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。 2、 状态：某一阶段的出发位置称为状态。

3、 决策：从某阶段的一个状态演变到下一个阶段某状态的选择。

4、 状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导

出了后一阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律，称为状态转移方程。

动态规划法的定义：在求解问题中，对于每一步决策，列出各种可能的局部解，

再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解，这种求解方法称为动态规划法。

一般来说，适合于用动态规划法求解的问题具有以下特点：

1、可以划分成若干个阶段，问题的求解过程就是对若干个阶段的一系列决策过

程。

2、每个阶段有若干个可能状态

3、一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态。 4、在任一个阶段，最佳的决策序列和该阶段以前的决策无关。

5、各阶段状态之间的转换有明确定义的费用，而且在选择最佳决策时有递推关系

（即动态转移方程）。

动态规划法所处理的问题是一个多阶段最优化决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线。如下图：

动态规划设计都有着一定的模式，一般要经历以下几个步骤： 1、划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。

2、确定状态：将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来。

3、确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态，所以如果确定了决策，状态转移方程也就可以写出。

4、寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件

或边界条件。

5、程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现

部分就会非常简单。

根据以上的步骤设计，可以得到动态规划设计的一般模式： for k:=阶段最小值to 阶段最大值do {顺推每一个阶段}

for I:=状态最小值to 状态最大值do {枚举阶段k的每一个状态}

for j:=决策最小值to 决策最大值do {枚举阶段k中状态i可选择的每一种

决策}

f[ik]:=min（max）{f[ik-1]+a[ik-1，jk-1]|ik-1通过决策jk-1可达ik}

有了以上的设计模式，对于简单的动态规划问题，就可以按部就班地进行动态规划设计。

例1：合唱队形（noip2004tg）

【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK，则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 【输入文件】输入文件chorus.in的第一行是一个整数N（2 <= N <= 100），表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti（130 <= Ti <= 230）是第i位同学的身高（厘米）。

【输出文件】输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。 【样例输入】8

186 186 150 200 160 130 197 220 【样例输出】 4

算法分析：此题采用动态规划法求解。先分别从左到右求最大上升子序列，从右到左求最大下降子序列，再枚举中间最高的一个人。算法实现起来也很简单，时间复杂度O(N^2)。

我们先考虑如何求最大上升子序列的长度，设f1(i)为前i个同学的最大上升子序列长度。若要求f1(i)，必须先求得f1(1),f1(2),…,f1(i-1)，再选择一个最大的f1(j)（j

设f2(i)为后面N-i+1位排列的最大下降子序列长度，用同样的方法可以得到状态转移方程：f2(i)=max{f2(j)+1} (i

t,f1,f2:array[1..100]of byte; i,j,n,max:integer; begin

assign(input,'chorus.in'); reset(input); readln(n); for i:=1 to n do begin

read(t[i]);f1[i]:=1;f2[i]:=1; end;{for}

close(input); max:=0; for i:=2 to n do

for j:=1 to i-1 do begin

if (t[i]>t[j])and(f1[j]>=f1[i]) then f1[i]:=f1[j]+1; {从左到右求最大上升子序列}

if (t[n-i+1]>t[n-j+1])and(f2[n-j+1]>=f2[n-i+1]) then f2[n-i+1]:=f2[n-j+1]+1; {从右到左求最大下降子序列} end;{for}

for i:=1 to n do if max

运用动态规划法求解问题的关键是找出状态转移方程，只要找出了状态转移方程，问题就解决了一半，剩下的事情就是解决如何把状态转移方程用程序实现。

例2、乘积最大（noip2000tg）

题目大意：在一个长度为N的数字串中插入r个乘号，将它分成r+1个部分，找出一种分法，使得这r+1个部分的乘积最大。

算法分析：此题满足动态规划法的求解标准，我们把它按插入的乘号数来划分阶段，若插入K个乘号，可把问题看做是K个阶段的决策问题。设f[i,k]表示在前i位数中插入K个乘号所得的最大值，a[i,j]表示从第i位到第j位所组成的自然数。用f[i,k]存储阶段K的每一个状态，可以得状态转移方程： f[i,k]=max{f[j,k-1]*a[j+1,i]}（k<=j<=i） 边界值：f[j,0]=a[1,j] (1

根据状态转移方程，我们就很容易写出动态规划程序： for k:=1 to r do for i:=k+1 to n do for j:=k to I do

if f[i,k]

近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOIP都至少有一道题目需要用动态规划法求解。而应用动态规划法解题是富于技巧性和创造性的，虽然在前面的求解过程中给出了一个解题的基本模式，但由于动态规划题目出现的形式多种多样，并且大部分题目表面上看不出与动态规划的直接联系，只有在充分把握其思想精髓的前提下大胆联想，多做多练才能达到得心应手，灵活运用的境界。

完

一、枚举法OK 二、回溯法 OK 三、递归法OK 四、递推法 OK 五、分治法OK 六、贪心法 OK 七、搜索法一OK 八、搜索法二OK 九、动态规划法 OK

本文来源：https://www.bwwdw.com/article/t5s.html