第四课 枚举法
所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。一般思路：
l 对命题建立正确的数学模型；
l 根据命题确定的数学模型中各变量的变化范围（即可能解的范围）；
l 利用循环语句、条件判断语句逐步求解或证明；
枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法。
例7：求满足表达式A+B=C的所有整数解，其中A，B，C为1~3之间的整数。
分析：本题非常简单，即枚举所有情况，符合表达式即可。算法如下：
for A := 1 to 3 do
for B := 1 to 3 do
for C := 1 to 3 do
if A + B = C then
Writeln(A, ‘+’, B, ‘=’, C);
上例采用的就是枚举法。所谓枚举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立的，即为解。
从枚举法的定义可以看出，枚举法本质上属于搜索。但与隐式图的搜索有所区别，在采用枚举法求解的问题时，必须满足两个条件：
① 预先确定解的个数n；
② 对每个解变量A1，A2，……，An的取值，其变化范围需预先确定
A1∈{X11，……，X1p}
……
Ai∈{Xi1，……，Xiq}
……
An∈{Xn1，……，Xnk}
例7中的解变量有3个：A，B，C。其中
A解变量值的可能取值范围A∈{1，2，3}
B解变量值的可能取值范围B∈{1，2，3}
C解变量值的可能取值范围C∈{1，2，3}
则问题的可能解有27个
（A，B，C）∈{（1，1，1），（1，1，2），（1，1，3），
（1，2，1），（1，2，2），（1，2，3），
………………………………
（3，3，1），（3，3，2），（3，3，3）}
在上述可能解集合中，满足题目给定的检验条件的解元素，即为问题的解。
如果我们无法预先确定解的个数或各解的值域，则不能用枚举，只能采用搜索等算法求解。由于回溯法在搜索每个可能解的枚举次数一般不止一次，因此，对于同样规模的问题，回溯算法要比枚举法时间复杂度稍高。
例8 给定一个二元一次方程aX+bY=c。从键盘输入a,b,c的数值，求X在[0，100]，Y在[0，100]范围内的所有整数解。
分析：要求方程的在一个范围内的解，只要对这个范围内的所有整数点进行枚举，看这些点是否满足方程即可。参考程序：
program exam8;
var
a,b,c:integer;
x,y:integer;
begin
write('Input a,b,c:');readln(a,b,c);
for x:=0 to 100 do
for y:=0 to 100 do
if a*x+b*y=c then writeln(x,' ',y);
end.
从上例可以看出，所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。
例9 巧妙填数
将1～9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍, 第三行的三位数是第一行的三倍, 应怎样填数。
|
1 |
9 |
2 |
|
3 |
8 |
4 |
|
5 |
7 |
6 |
如图6:
图6
分析：本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。
但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。因此设计参考程序：
program exam9;
var
i,j,k,s:integer;
function sum(s:integer):integer;
begin
sum:=s div 100 + s div 10 mod 10 + s mod 10
end;
function mul(s:integer):longint;
begin
mul:=(s div 100) * (s div 10 mod 10) * (s mod 10)
end;
begin
for i:=1 to 3 do
for j:=1 to 9 do
if j<>i then for k:=1 to 9 do
if (k<>j) and (k<>i) then begin
s := i*100 + j*10 +k; {求第一行数}
if 3*s<1000 then
if (sum(s)+sum(2*s)+sum(3*s)=45) and
(mul(s)*mul(2*s)*mul(3*s)=362880) then {满足条件，并数字都由1~9组成}
begin
writeln(s);
writeln(2*s);
writeln(3*s);
writeln;
end;
end;
end.
例10 在某次数学竞赛中, A、B、C、D、E五名学生被取为前五名。请据下列说法判断出他们的具体名次, 即谁是第几名？
条件1: 你如果认为A, B, C, D, E 就是这些人的第一至第五名的名次排列, 便大错。因为:
没猜对任何一个优胜者的名次。
也没猜对任何一对名次相邻的学生。
条件2: 你如果按D, A , E , C , B 来排列五人名次的话, 其结果是:
说对了其中两个人的名次。
还猜中了两对名次相邻的学生的名次顺序。
分析：本题是一个逻辑判断题，一般的逻辑判断题都采用枚举法进行解决。5个人的名次分别可以有5！=120种排列可能，因为120比较小，因此我们对每种情况进行枚举，然后根据条件判断哪些符合问题的要求。
根据已知条件，A<>1,B<>2,C<>3,D<>4,E<>5,因此排除了一种可能性，只有4！=24种情况了。
参考程序：
Program Exam10;
Var
A,B,C,D,E :Integer;
Cr :Array[1..5] Of Char;
Begin
For A:=1 To 5 Do
For B:=1 To 5 Do
For C:=1 To 5 Do
For D:=1 To 5 Do
For E:=1 To 5 Do Begin
{ABCDE没猜对一个人的名次}
If (A=1) Or (B=2) Or (C=3) Or (D=4) Or (E=5) Then Continue;
If [A,B,C,D,E]<>[1,2,3,4,5] Then Continue;{他们名次互不重复}
{DAECB猜对了两个人的名次}
If Ord(A=2)+Ord(B=5)+Ord(C=4)+Ord(D=1)+Ord(E=3)<>2 Then Continue;
{ABCDE没猜对一对相邻名次}
If (B=A+1) Or (C=B+1) Or (D=C+1) Or (E=D+1) Then Continue;
{DAECB猜对了两对相邻人名次}
If Ord(A=D+1)+Ord(E=A+1)+Ord(C=E+1)+Ord(B=C+1)<>2 Then Continue;
Cr[A]:='A';Cr[B]:='B';Cr[C]:='C';
Cr[D]:='D';Cr[E]:='E';
Writeln(Cr[1],' ',Cr[2],' ',Cr[3],' ',Cr[4],' ',Cr[5]);
End;
End.
例11：来自不同国家的四位留学生A,B,C,D在一起交谈,他们只会中、英、法、日四种语言中的2种,情况是, 没有人既会日语又会法语;A会日语,但D不会,A和D能互相交谈,B不会英语,但A和C交谈时却要B当翻译,B,C,D三个想互相交谈,但找不到共同的语言,只有一种语言3人都会,编程确定A,B,C,D四位留学生各会哪两种语言。
分析：将中、法、日、英四种语言分别定义为CHN、FRH、JPN、ENG,则四种语言中取两种共有(CHN,ENG),（CHN,FRH）,(CHN,JPN),( ENG,FRH),( ENG,JPN),(FRH,JPN)六种组合，分别定义为1、2、3、4、5、6。据已知，没有人既会日语又会法语;因此，组合6不会出现；A 会日语，所以A只可能等于3、5；D不会日语, 所以D只可能等于1、2、4；B不会英语，所以B只可能等于2、3；见下表。如果我们对A、B、C、D分别进行枚举，根据判定条件，即可找到答案。
|
|
(CHN,ENG) |
(CHN,FRH) |
(CHN,JPN) |
( ENG,FRH) |
( ENG,JPN) |
|
A |
× |
× |
|
× |
|
|
B |
× |
|
|
× |
× |
|
C |
|
|
|
|
|
|
D |
|
|
× |
|
× |
程序如下：
program EXAM11;
type
Language = (CHN,ENG,FRH,JPN);
TNoSet= set of Language;
const
No: array [1 .. 5] of TNoSet=
([CHN,ENG], [CHN,FRH], [CHN,JPN], [ENG,FRH], [ENG,JPN]);
var
A, B, C, D: 1 .. 5;
Can1, Can2, Can3, Can4: Boolean;
function Might(Lang: Language): Boolean;
var
Bool: Boolean;
begin
Bool:=false;
if No[A] * No[A] * No[C] = [Lang] then Bool := True;
if No[A] * No[B] * No[D] = [Lang] then Bool := True;
if No[A] * No[C] * No[D] = [Lang] then Bool := True;
if No[B] * No[C] * No[D] = [Lang] then Bool := True;
Might := Bool
end;
procedure Print(A, B, C, D: Integer);
procedure Show(P: Integer; Ch: Char);
var
I: Integer;
Lang: Language;
begin
Write(ch,':');
for Lang := CHN to JPN do
if Lang in No[P] then
case Lang of
CHN: Write('CHN':5);
FRH: Write('FRH':5);
JPN: Write('JPN':5);
ENG: Write('ENG':5);
end;
Writeln;
end;
begin
Show(A, 'A');
Show(B, 'B');
Show(C, 'C');
Show(D, 'D');
end;
begin
for A := 3 to 5 do
if A <> 4 then for B := 2 to 3 do
for C := 1 to 5 do
for D := 1 to 4 do if D <> 3 then begin
{A和D能互相交谈}
Can1 := No[A] * No[D] <> [];
{A和C交谈时却要B当翻译}
Can2 := (No[A] * No[C] = []) and (No[A] * No[B] <> [])
and (No[B] * No[C] <> []);
{B,C,D三个想互相交谈,但找不到共同的语言}
Can3 := No[B] * No[C] * No[D] = [];
{只有一种语言3人都会}
Can4 := Ord(Might(CHN)) + Ord(Might(ENG))
+ Ord(Might(FRH)) + Ord(Might(JPN)) = 1;
if Can1 and Can2 and Can3 and Can4 then Print(A,B,C,D);
end;
end.
例12 古纸残篇
在一位数学家的藏书中夹有一张古旧的纸片。纸片上的字早已模糊不清了, 只留下曾经写过字的痕迹, 依稀还可以看出它是一个乘法算式, 如图7所示。这个算式上原来的数字是什么呢？夹着这张纸片的书页上,“素数”两个字被醒目的划了出来。难道说, 这个算式与素数有什么关系吗？有人对此作了深入的研究, 果然发现这个算式中的每一个数字都是素数, 而且这样的算式是唯一的。请你也研究一番, 并把这个算式写出来。
分析：实际上，只要知道乘数和被乘数就可以写出乘法算式，所以我们可以枚举乘数与被乘数的每一位。然后再判断是不是满足条件即可。计算量是45=1024，对于计算机来说，计算量非常小。
参考程序：
Program Exam12;
Const
Su : Array[1..4] Of Longint=(2,3,5,7);
Var
A1,A2,A3,B1,B2,X,Y,S :Longint;
Function Kx(S:Longint):Boolean;{判断一个数
是不是都是由素数组成}
Begin
Kx:=True;
While S<>0 Do Begin
If Not((S Mod 10) In [2,3,5,7]) Then Begin
Kx:=False;
Exit;
End;
S:=S Div 10;
End;
End;
Begin
For A1:=1 To 4 Do
For A2:=1 To 4 Do
For A3:=1 To 4 Do
For B1:=1 To 4 Do
For B2:=1 To 4 Do Begin
X:=Su[A1]*100+Su[A2]*10+Su[A3];{X为被乘数}
If X*Su[B1]<1000 Then Continue;
If X*Su[B2]<1000 Then Continue;
If X*(Su[B1]*10+Su[B2])<10000 Then Continue;
{它们分别是两个四位数，一个五位数}
If (Kx(X*Su[B1])=False) Or
(Kx(X*Su[B2])=False) Or
(Kx(X*(Su[B1]*10+Su[B2]))=False) Then Continue;
{满足其他数都是由质数构成}
Writeln(' ',Su[A1],Su[A2],Su[A3]);
Writeln('* ',Su[B1],Su[B2]);
Writeln('-----------');
Writeln(' ',X*Su[B2]);
Writeln(' ',X*Su[B1]);
Writeln('-----------');
Writeln(' ',X*(Su[B1]*10+Su[B2]));
End;
End.
例13：时钟问题（IOI94-4）
在图8所示的3*3矩阵中有9个时钟，我们的目标是旋转时钟指针，使所有时钟的指针都指向12点。允许旋转时钟指针的方法有9种，每一种移动用一个数字号（1，2，…，9）表示。图2-11示出9个数字号与相应的受控制的时钟，这些时钟在图中以灰色标出，其指针将顺时针旋转90度。
输入数据：
由输入文件INPUT.TXT读9个数码，这些数码给出了9个时钟时针的初始位置。数码与时刻的对应关系为：
0——12点
1——3点
2——6点
3——9点
图2-11中的例子对应下列输入数据：
330
222
212
输出数据：
将一个最短的移动序列（数字序列）写入输出文件OUTPUT.TXT中，该序列要使所有的时钟指针指向12点，若有等价的多个解，仅需给出其中一个。在我们的例子中，相应的OUTPUT.TXT的内容为：
5849
输入输出示例：
|
INPUT.TXT |
OUTPUT.TXT |
|
330 222 212 |
5489 |
具体的移动方案如图10所示。
分析：
首先，我们分析一下表示时钟时针初始位置的数码j（0≦j≦3）与时刻的对应关系：
0——12点
1——3点
2——6点
3——9点
每移动一次，时针将顺时针旋转90度。由此我们可以得出：
对于任意一个时钟i（1≦i≦9）来说，从初始位置j出发至少需要Ci=（4-j） mod 4次操作，才能使得时针指向12点。而对每种移动方法要么不采用，要么采用1次、2次或3次，因为操作四次以后，时钟将重复以前状态。因此，9种旋转方案最多产生49个状态。
移动方案选取与顺序无关。样例中，最佳移动序列为5849，同样4589序列也可达到目标。因此，求解过程中可以直接选取序列中从小至大排列的移动序列即可。
设 pi表示第i种旋转方法的使用次数（0≦pi≦3，1≦i≦9）。
则可能的解的集合为{P1，P2，……，P9}，该集合共含49个状态。从图2.11中，我们可以分析出9个时钟分别被哪些方法所控制，见下表：
|
时钟号 |
控制时钟方案 |
检验条件 |
|
1 |
1、2、4 |
C1=(P1+P2+P4) mod 4 |
|
2 |
1、2、3、5 |
C2=(P1+P2+P3+P5) mod 4 |
|
3 |
2、3、6 |
C3=(P2+P3+P6) mod 4 |
|
4 |
1、4、5、7 |
C4=(P1+P4+P5+P7) mod 4 |
|
5 |
1、3、5、7、9 |
C5=(P1+P3+P5+P7+P9) mod 4 |
|
6 |
3、5、6、9 |
C6=(P3+P5+P6+P9) mod 4 |
|
7 |
4、7、8 |
C7=(P4+P7+P8) mod 4 |
|
8 |
5、7、8、9 |
C8=(P5+P7+P8+P9) mod 4 |
|
9 |
6、8、9 |
C9=(P6+P8+P9) mod 4 |
因此我们可以设计如下枚举算法：
for p1:=0 to 3 do
for p2:=0 to 3 do
... ... ...
for p9:=0 to 3 do
if c1满足时钟1 and c2满足时钟2 and ... and c9满足时钟9 then
打印解路径；
显然，上述枚举算法枚举了所有49=262144个状态，运算量和运行时间颇大。我们可以采取缩小可能解范围的局部枚举法，仅枚举第1、2、3种旋转方法可能取的43个状态，根据这三种旋转方法的当前状态值，由下述公式
P4=order(C1-P1-P2);
P5=order(C2-P1-P2-P3);
P6=order(C3-P2-P3);
P7=order(C4-P1-P4-P5);
P8=order(C8-P5-PP9);
P9=order(C6-P3-P5-P6);
其中
得出其余P4……P9的相应状态值。然后将P1，P2，…，P9代入下述三个检验条件
C5=(P1+P3+P5+P7+P9) mod 4
C7=(P4+P7+P8) mod 4
C9=(P6+P8+P9) mod 4
一一枚举，以求得确切解。
由此可见，上述局部枚举的方法（枚举状态数为43个）比较全部枚举的方法（枚举状态数为49个）来说，由于大幅度削减了枚举量，减少运算次数，因此其时效显著改善，是一种优化了的算法。
程序如下：
program IOI94_4;
const
Inp = 'input.txt';
Outp = 'output.txt';
var
Clock, Map: array [1 .. 3, 1 .. 3] of Integer;
{Clock：第((I+2)mod 3)*3+J个时钟从初始时间到12点的最少移动次数}
{Map:最短移动序列中，数字（（I+2）mod 3）*3+J的次数}
procedure Init;
var
I, J: Integer;
begin
Assign(Input, Inp); Reset(Input);
for I := 1 to 3 do
{读入9个时钟指针的初始位置，求出每个时钟从初始到12点的最少移动次数}
for J := 1 to 3 do begin
Read(Clock[I, J]);
Clock[I, J] := (4 - Clock[I, J]) mod 4;
end;
Close(Input);
end;
function Order(K: Integer): Integer;
var
c: Integer;
begin
c:=k;
while c<0 do inc(c,4);
while c>4 then dec(c,4);
Order := k;
end;
procedure Main; {计算和输出最短移动序列}
var
I, J, K: Integer;
begin
{枚举最短移动序列中数字1、2、3的个数可能取的43种状态}
Assign(Output, Outp); Rewrite(Output);
for Map[1, 1] := 0 to 3 do
for Map[1, 2] := 0 to 3 do
for Map[1, 3] := 0 to 3 do begin
Map[2,1]:=Order(Clock[1,1]-Map[1,1]-Map[1,2]);
Map[2,3]:=Order(Clock[1,3]-Map[1,2]-Map[1,3]);
Map[2,2]:=Order(Clock[1,2]-Map[1,1]-Map[1,2]-Map[1, 3]);
Map[3,1]:=Order(Clock[2,1]-Map[1,1]-Map[2,1]-Map[2, 2]);
Map[3,3]:=Order(Clock[2,3]-Map[1,3]-Map[2,2]-Map[2, 3]);
Map[3,2]:=Order(Clock[3,2]-Map[3,1]-Map[3,3]-Map[2, 2]);
{根据数字1、2、3个数的当前值，得出数字4~9的个数}
if ((Map[2,1]+Map[3,1]+Map[3,2])mod 4=Clock[3,1]) and
((Map[2,3]+Map[3,2]+Map[3,3])mod 4=Clock[3, 3])and
((Map[2,2]+Map[1,1]+Map[1,3]+Map[3,1]+Map[3, 3])
mod 4 = Clock[2, 2])
then begin {若数字4~9的个数满足检验条件，则输出方案}
for I := 1 to 3 do
for J := 1 to 3 do
for K := 1 to Map[I, J] do
Write((I - 1) * 3 + J);
Exit; {找到一个解后退出}
end;
end;
Writeln('No Answer !');
Close(Output);
end;
begin
Init;
Main;
end.
在上例中，由于事先能够排除那些明显不属于解集的元素，使得算法效率非常高。而减少重复运算、力求提前计算所需数据、使用恰当的数据结构进行算法优化等方法也是优化枚举算法的常用手段。
例14：最佳游览线路 （NOI94）
某旅游区的街道成网格状（图2.13）。其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道，游客在旅游街上只能从西向东走，在林阴道上则既可从南向北走，也可以从北向南走。
阿龙想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的街道值得游览的程度，分值时从-100到100的整数，所有林阴道不打分。所有分值不可能全是负分。
例如图11是被打过分的某旅游区的街道图：
阿龙可以从任一个路口开始游览，在任一个路口结束游览。请你写一个程序，帮助阿龙找一条最佳的游览线路，使得这条线路的所有分值总和最大。
输入数据：
输入文件是INPUT.TXT。文件的第一行是两个整数M和N，之间用一个空格符隔开，M表示有多少条旅游街（1≦M≦100），N表示有多少条林阴道（1≦M≦20001）。接下来的M行依次给出了由北向南每条旅游街的分值信息。每行有N-1个整数，依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。
输出数据：
输出文件是OUTPUT.TXT。文件只有一行，是一个整数，表示你的程序找到的最佳游览线路的总分值。
输入输出示例：
|
INPUT.TXT |
OUTPUT.TXT |
|
3 6 -50 –47 36 –30 –23 17 –19 –34 –13 –8 -42 –3 –43 34 –45 |
84 |
分析：
设Lij为第I条旅游街上自西向东第J段的分值（1 ≦ I ≦ M，1 ≦ J ≦ N – 1）。例如样例中L12=17，L23=-34，L34=34。
我们将网格状的旅游区街道以林荫道为界分为N – 1个段，每一段由M条旅游街的对应段成，即第J段成为{L1J，L2J，……，LMJ}（1≦ J ≦ N – 1）。由于游览方向规定横向自西向东，纵向即可沿林阴道由南向北，亦可由北向南，而横行的街段有分值，纵行无分值，因此最佳游览路现必须具备如下三个特征：
① 来自若干个连续的段，每一个段中取一个分值；
② 每一个分值是所在段中最大的；
③ 起点段和终点段任意，但途经段的分值和最大。
设Li为第I个段中的分值最大的段。即Li=Max{L1I，L2I，……，LMI}（1≦I≦N – 1）。例如对于样例数据：
L1=Max（-50，17，-42）=17；
L2=Max（-47，-19，-3）=-3；
L3=Max（36，-34，-43）=36；
L4=Max（-30，-13，34）=34；
L5=Max（-23，-8，-45）=-8；
有了以上的基础，我们便可以通过图示描述解题过程，见图12。
我们把将段设为顶点，所在段的最大分值设为顶点的权，各顶点按自西向东的顺序相连，组成一条游览路线。显然，如果确定西端为起点、东段为终点，则这条游览路线的总分值最大。
问题是某些段的最大分值可能是负值，而最优游览路线的起点和终点任意，在这种情况下，上述游览路线就不一定最佳了。因此，我们只能枚举这条游览路线的所有可能的子路线，从中找出一条子路线IàI+1à……àJ（1 ≦ I<J ≦ N – 1），使得经过顶点的权和LI+LI+1+……+LJ最大。
设Best为最佳游览路线的总分值，初始时为0；
Sum为当前游览路线的总分值。
我们可以得到如下算法：
Best := 0; Sum := 0;
for I := 1 to N – 2 do
for J := I + 1 to N – 1 do begin
Sum := LI + …… + LJ;
if Sum > Best then
Best := Sum;
end
显然，这个算法的时间复杂度为O（N2）。而N在1~20001之间，时间复杂度比较高。于是，我们必须对这个算法进行优化。
仍然从顶点1开始枚举最优路线。若当前子路线延伸至顶点I时发现总分值Sum≦0，则应放弃当前子路线。因为无论LI+1为何值，当前子路线延伸至顶点I+1后的总分值不会大于LI+1。因此应该从顶点I+1开始重新考虑新的一条子路线。通过这种优化，可以使得算法的时间复杂度降到了O（N）。
优化后的算法描述如下:
Best := 0; Sum := 0;
for I := 1 to N – 1 do begin
Sum := Sum + LI;
if Sum > Best then
Best := Sum;
if Sum < 0 then
Sum := 0;
end
程序描述如下：
{$R-,S-,Q-}
{$M 65520,0,655360}
program Noi94;
const
MaxN = 20001; {林阴道数的上限}
Inp = 'input.txt';
Outp = 'output.txt';
var
M, N: Word; {旅游街数和林阴道数}
Best: Longint; {最佳游览路线的总分值}
Score: array [1..MaxN] of ShortInt; {描述每个段的最大分值}
procedure Init;
var
I, J, K: Integer;
Buffer: array [1 .. 40960] of Char; {文件缓冲区}
begin
Assign(Input, Inp);
Reset(Input);
SetTextBuf(Input, Buffer); {开辟文件缓冲区}
Readln(M, N); {读入旅游街数和林阴道数}
FillChar(Score,Sizeof(Score),$80); {初始化各段的最大分值}
for I := 1 to M do {计算1~N –1段的最大分值 }
for J := 1 to N - 1 do begin
Read(K);
if K > Score[J] then Score[J] := K;
end;
Close(Input);
end;
procedure Out;
begin
Assign(Output, Outp);
Rewrite(Output);
Writeln(Best);
Close(Output);
end;
procedure Main;
var
I: Integer;
Sum: Longint; {当前游览路线的总分值}
begin
{最佳游览路线的总分值和当前游览路线的总分值初始化}
Best := 0;
Sum := 0;
for I := 1 to N - 1 do begin {顺序枚举游览路线的总分值}
Inc(Sum, Score[I]); {统计当前游览路线的总分值}
if Sum > Best then Best := Sum; {若当前最佳，则记下}
if Sum < 0 then Sum := 0; {若总分值<0，则考虑一条新路线}
end;
end;
begin
Init; {输入数据}
Main; {主过程}
Out; {输出}
end.
- 版权所有 www.hnsz.net all rights reserved.power by 现代教育技术中心------淮南第三中学
- 皖ICP备2021013132号-1 网页设计、网站制作均由淮南三中信息中心提供支持
