《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 枚舉法二.doc》由會員分享，可在線閱讀，更多相關(guān)《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 枚舉法二.doc（15頁珍藏版）》請在裝配圖網(wǎng)上搜索。

2019-2020 年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 枚舉法二 課題：枚舉法 目標(biāo)： 知識目標(biāo)：枚舉算法的本質(zhì)和應(yīng)用 能力目標(biāo)：枚舉算法的應(yīng)用！ 重點：利用枚舉算法解決實際問題 難點：枚舉算法的次數(shù)確定 板書示意： 1） 簡單枚舉（例 7、例 8、例 9） 2） 利用枚舉解決邏輯判斷問題（例 10、例 11） 3） 枚舉解決競賽問題（例 12、例 13、例 14） 授課過程： 所謂枚舉法,指的是從可能的解集合中一一枚舉各元素,用題目給定的檢驗條件判定哪 些是無用的,哪些是有用的.能使命題成立,即為其解。一般思路： ? 對命題建立正確的數(shù)學(xué)模型； ? 根據(jù)命題確定的數(shù)學(xué)模型中各變量的變化范圍（即可能解的范圍） ； ? 利用循環(huán)語句、條件判斷語句逐步求解或證明； 枚舉法的特點是算法簡單，但有時運算量大。對于可能確定解的值域又一時找不到其他更 好的算法時可以采用枚舉法。 例 7：求滿足表達(dá)式 A+B=C 的所有整數(shù)解，其中 A，B，C 為 1~3 之間的整數(shù)。 分析：本題非常簡單，即枚舉所有情況，符合表達(dá)式即可。算法如下： 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); 上例采用的就是枚舉法。所謂枚舉法，指的是從可能的解的集合中一一枚舉各元素， 用題目給定的檢驗條件判定哪些是無用的，哪些是有用的。能使命題成立的，即為解。 從枚舉法的定義可以看出，枚舉法本質(zhì)上屬于搜索。但與隱式圖的搜索有所區(qū)別，在 采用枚舉法求解的問題時，必須滿足兩個條件： ① 預(yù)先確定解的個數(shù) n； ② 對每個解變量 A1，A2，……，An 的取值，其變化范圍需預(yù)先確定 A1∈{X 11，……，X 1p} …… Ai∈{X i1，……，X iq} …… An∈{X n1，……，X nk} 例 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）} 在上述可能解集合中，滿足題目給定的檢驗條件的解元素，即為問題的解。 如果我們無法預(yù)先確定解的個數(shù)或各解的值域，則不能用枚舉，只能采用搜索等算法 求解。由于回溯法在搜索每個可能解的枚舉次數(shù)一般不止一次，因此，對于同樣規(guī)模的問 題，回溯算法要比枚舉法時間復(fù)雜度稍高。 例 8 給定一個二元一次方程 aX+bY=c。從鍵盤輸入 a,b,c 的數(shù)值，求 X 在[0，100]， Y 在[0，100]范圍內(nèi)的所有整數(shù)解。 分析：要求方程的在一個范圍內(nèi)的解，只要對這個范圍內(nèi)的所有整數(shù)點進行枚舉，看 這些點是否滿足方程即可。參考程序： 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 巧妙填數(shù) 將 1～9 這九個數(shù)字填入九個空格中。每一橫行的三個數(shù)字組成一個三位數(shù)。如果要使 第二行的三位數(shù)是第一行的兩倍, 第三行的三位數(shù)是第一行的三倍, 應(yīng)怎樣填數(shù)。如圖 6: 圖 6 分析：本題目有 9 個格子，要求填數(shù)，如果不考慮問題給出的條件，共有 9！=362880 種方 案，在這些方案中符合問題條件的即為解。因此可以采用枚舉法。 1 9 2 3 8 4 5 7 6 但仔細(xì)分析問題，顯然第一行的數(shù)不會超過 400，實際上只要確定第一行的數(shù)就可以根據(jù) 條件算出其他兩行的數(shù)了。這樣僅需枚舉 400 次。因此設(shè)計參考程序： 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 ji then for k:=1 to 9 do if (kj) and (ki) then begin s := i*100 + j*10 +k; {求第一行數(shù)} 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 {滿足條件，并數(shù)字都由 1~9 組成} begin writeln(s); writeln(2*s); writeln(3*s); writeln; end; end; end. 例 10 在某次數(shù)學(xué)競賽中, A、B、C、D、E 五名學(xué)生被取為前五名。請據(jù)下列說法判斷 出他們的具體名次, 即誰是第幾名？ 條件 1: 你如果認(rèn)為 A, B, C, D, E 就是這些人的第一至第五名的名次排列 , 便大錯。因 為: 沒猜對任何一個優(yōu)勝者的名次。 也沒猜對任何一對名次相鄰的學(xué)生。 條件 2: 你如果按 D, A , E , C , B 來排列五人名次的話, 其結(jié)果是: 說對了其中兩個人的名次。 還猜中了兩對名次相鄰的學(xué)生的名次順序。 分析：本題是一個邏輯判斷題，一般的邏輯判斷題都采用枚舉法進行解決。5 個人的 名次分別可以有 5！=120 種排列可能，因為 120 比較小，因此我們對每種情況進行枚 舉，然后根據(jù)條件判斷哪些符合問題的要求。 根據(jù)已知條件，A1,B2,C3,D4,E5,因此排除了一種可能性，只有 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;{他們名次互不重復(fù)} {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：來自不同國家的四位留學(xué)生 A,B,C,D 在一起交談,他們只會中、英、法、日四 種語言中的 2 種,情況是, 沒有人既會日語又會法語;A 會日語,但 D 不會,A 和 D 能互相交談,B 不會英語,但 A 和 C 交談時卻要 B 當(dāng)翻譯,B,C,D 三個想互相交談,但找不到共同的語言,只 有一種語言 3 人都會,編程確定 A,B,C,D 四位留學(xué)生各會哪兩種語言。 分析：將中、法、日、英四種語言分別定義為 CHN、FRH、JPN、ENG,則四種語言中取 兩種共有(CHN,ENG),（CHN,FRH）,(CHN,JPN),( ENG,FRH),( ENG,JPN),(FRH,JPN)六種組合， 分別定義為 1、2、3、4、5、6。據(jù)已知，沒有人既會日語又會法語;因此，組合 6 不會出 現(xiàn)；A 會日語，所以 A 只可能等于 3、5；D 不會日語, 所以 D 只可能等于 1、2、4；B 不會 英語，所以 B 只可能等于 2、3；見下表。如果我們對 A、B、C、D 分別進行枚舉，根據(jù)判 定條件，即可找到答案。 (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 * * * * * * * * * * * * * * * * * * 圖 7 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 當(dāng)翻譯} 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 古紙殘篇 在一位數(shù)學(xué)家的藏書中夾有一張古舊的紙片。紙片上的字早已模糊不清了, 只留下曾經(jīng)寫 過字的痕跡, 依稀還可以看出它是一個乘法算式, 如圖 7 所示。這個算式上原來的數(shù)字是 什么呢？夾著這張紙片的書頁上,“素數(shù)”兩個字被醒目的劃了出來。難道說, 這個算式與 素數(shù)有什么關(guān)系嗎？有人對此作了深入的研究, 果然發(fā)現(xiàn)這個算 式中的每一個數(shù)字都是素數(shù), 而且這樣的算式是唯一的。請你也 研究一番, 并把這個算式寫出來。 分析：實際上，只要知道乘數(shù)和被乘數(shù)就可以寫出乘法算式，所以我們可以枚舉乘數(shù)與被 乘數(shù)的每一位。然后再判斷是不是滿足條件即可。計算量是 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;{判斷一個數(shù) 是不是都是由素數(shù)組成} Begin Kx:=True; While S0 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 為被乘數(shù)} If X*Su[B1]<1000 Then Continue; If X*Su[B2]<1000 Then Continue; If X*(Su[B1]*10+Su[B2])<10000 Then Continue; {它們分別是兩個四位數(shù)，一個五位數(shù)} If (Kx(X*Su[B1])=False) Or (Kx(X*Su[B2])=False) Or (Kx(X*(Su[B1]*10+Su[B2]))=False) Then Continue; {滿足其他數(shù)都是由質(zhì)數(shù)構(gòu)成} 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 個時鐘，我們的目標(biāo)是旋轉(zhuǎn)時鐘指針，使所有時鐘的指 針都指向 12 點。允許旋轉(zhuǎn)時鐘指針的方法有 9 種，每一種移動用一個數(shù)字號 （1，2，…，9）表示。圖 2-11 示出 9 個數(shù)字號與相應(yīng)的受控制的時鐘，這些時鐘在圖中 以灰色標(biāo)出，其指針將順時針旋轉(zhuǎn) 90 度。 輸入數(shù)據(jù)： 由輸入文件 INPUT.TXT 讀 9 個數(shù)碼，這些數(shù)碼給出了 9 個時鐘時針的初始位置。數(shù)碼 與時刻的對應(yīng)關(guān)系為： 0——12 點 1——3 點 2——6 點 3——9 點 圖 2-11 中的例子對應(yīng)下列輸入數(shù)據(jù)： 330 222 212 輸出數(shù)據(jù)： 將一個最短的移動序列（數(shù)字序列）寫入輸出文件 OUTPUT.TXT 中，該序列要使所有的 時鐘指針指向 12 點，若有等價的多個解，僅需給出其中一個。在我們的例子中，相應(yīng)的 OUTPUT.TXT 的內(nèi)容為： 5849 圖 8 九種時鐘狀態(tài) 圖 9 九種被控制方式 輸入輸出示例： INPUT.TXT OUTPUT.TXT 330 222 212 5489 具體的移動方案如圖 10 所示。 分析： 首先，我們分析一下表示時鐘時針初始位置的數(shù)碼 j（0≦j≦3）與時刻的對應(yīng)關(guān)系： 0——12 點 1——3 點 2——6 點 3——9 點 每移動一次，時針將順時針旋轉(zhuǎn) 90 度。由此我們可以得出： 對于任意一個時鐘 i（1≦i≦9）來說，從初始位置 j 出發(fā)至少需要 Ci=（4-j） mod 4 次操作，才能使得時針指向 12 點。而對每種移動方法要么不采用，要么采用 1 次、2 次或 3 次，因為操作四次以后，時鐘將重復(fù)以前狀態(tài)。因此，9 種旋轉(zhuǎn)方案最多產(chǎn)生 49個狀態(tài)。 移動方案選取與順序無關(guān)。樣例中，最佳移動序列為 5849，同樣 4589 序列也可達(dá)到目 標(biāo)。因此，求解過程中可以直接選取序列中從小至大排列的移動序列即可。 設(shè) p i表示第 i 種旋轉(zhuǎn)方法的使用次數(shù)（0≦p i≦3，1≦i≦9） 。 則可能的解的集合為{P 1，P 2，……，P 9}，該集合共含 49個狀態(tài)。從圖 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 因此我們可以設(shè)計如下枚舉算法： for p1:=0 to 3 do for p2:=0 to 3 do 圖 10 示例移動方案 ... ... ... for p9:=0 to 3 do if c1 滿足時鐘 1 and c2 滿足時鐘 2 and ... and c9 滿足時鐘 9 then 打印解路徑； 顯然，上述枚舉算法枚舉了所有 49=262144 個狀態(tài)，運算量和運行時間頗大。我們可以 采取縮小可能解范圍的局部枚舉法，僅枚舉第 1、2、3 種旋轉(zhuǎn)方法可能取的 43個狀態(tài)，根 據(jù)這三種旋轉(zhuǎn)方法的當(dāng)前狀態(tài)值，由下述公式 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); 其中 ????????04mod)()cNcorde 得出其余 P4……P9的相應(yīng)狀態(tài)值。然后將 P1，P 2，…，P 9代入下述三個檢驗條件 C5=(P1+P3+P5+P7+P9) mod 4 C7=(P4+P7+P8) mod 4 C9=(P6+P8+P9) mod 4 一一枚舉，以求得確切解。 由此可見，上述局部枚舉的方法（枚舉狀態(tài)數(shù)為 43個）比較全部枚舉的方法（枚舉狀 態(tài)數(shù)為 49個）來說，由于大幅度削減了枚舉量，減少運算次數(shù)，因此其時效顯著改善，是 一種優(yōu)化了的算法。 程序如下： 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 點的最少移動次數(shù)} {Map:最短移動序列中，數(shù)字（（I+2）mod 3）*3+J 的次數(shù)} procedure Init; var I, J: Integer; begin Assign(Input, Inp); Reset(Input); for I := 1 to 3 do {讀入 9 個時鐘指針的初始位置，求出每個時鐘從初始到 12 點的最少移動次數(shù)} 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 c4 then dec(c,4); Order := k; end; procedure Main; {計算和輸出最短移動序列} var I, J, K: Integer; begin {枚舉最短移動序列中數(shù)字 1、2、3 的個數(shù)可能取的 43種狀態(tài)} 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]); {根據(jù)數(shù)字 1、2、3 個數(shù)的當(dāng)前值，得出數(shù)字 4~9 的個數(shù)} 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 {若數(shù)字 4~9 的個數(shù)滿足檢驗條件，則輸出方案} 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. 在上例中，由于事先能夠排除那些明顯不屬于解集的元素，使得算法效率非常高。而 減少重復(fù)運算、力求提前計算所需數(shù)據(jù)、使用恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)進行算法優(yōu)化等方法也是優(yōu) 化枚舉算法的常用手段。 例 14：最佳游覽線路 （NOI94） 某旅游區(qū)的街道成網(wǎng)格狀（圖 2.13） 。其中東西向的街道都是旅游街，南北向的街道都 是林蔭道。由于游客眾多，旅游街被規(guī)定為單行道，游客在旅游街上只能從西向東走，在 林陰道上則既可從南向北走，也可以從北向南走。 阿龍想到這個旅游區(qū)游玩。他的好友阿福給了他一些建議，用分值表示所有旅游街相 鄰兩個路口之間的街道值得游覽的程度，分值時從-100 到 100 的整數(shù)，所有林陰道不打分。 所有分值不可能全是負(fù)分。 例如圖 11 是被打過分的某旅游區(qū)的街道圖： 阿龍可以從任一個路口開始游覽，在任一個路口結(jié)束游覽。請你寫一個程序，幫助阿 龍找一條最佳的游覽線路，使得這條線路的所有分值總和最大。 輸入數(shù)據(jù)： 輸入文件是 INPUT.TXT。文件的第一行是兩個整數(shù) M 和 N，之間用一個空格符隔開，M 表示有多少條旅游街（1≦M≦100） ，N 表示有多少條林陰道（1≦M≦xx1） 。接下來的 M 行 依次給出了由北向南每條旅游街的分值信息。每行有 N-1 個整數(shù)，依次表示了自西向東旅 游街每一小段的分值。同一行相鄰兩個數(shù)之間用一個空格隔開。 輸出數(shù)據(jù)： 輸出文件是 OUTPUT.TXT。文件只有一行，是一個整數(shù)，表示你的程序找到的最佳游覽 線路的總分值。 輸入輸出示例： 圖 11 某旅游區(qū)街道示例圖 INPUT.TXT OUTPUT.TXT 3 6 -50 –47 36 –30 –23 17 –19 –34 –13 –8 -42 –3 –43 34 –45 84 分析： 設(shè) Lij為第 I 條旅游街上自西向東第 J 段的分值（1 ≦ I ≦ M，1 ≦ J ≦ N – 1） 。 例如樣例中 L12=17，L 23=-34，L 34=34。 我們將網(wǎng)格狀的旅游區(qū)街道以林蔭道為界分為 N – 1 個段，每一段由 M 條旅游街的對 應(yīng)段成，即第 J 段成為{L 1J，L 2J，……，L MJ}（1≦ J ≦ N – 1） 。由于游覽方向規(guī)定橫向 自西向東，縱向即可沿林陰道由南向北，亦可由北向南，而橫行的街段有分值，縱行無分 值，因此最佳游覽路現(xiàn)必須具備如下三個特征： ① 來自若干個連續(xù)的段，每一個段中取一個分值； ② 每一個分值是所在段中最大的； ③ 起點段和終點段任意，但途經(jīng)段的分值和最大。 設(shè) Li為第 I 個段中的分值最大的段。即 Li=Max{L1I，L 2I，……，L MI}（1≦I≦N – 1） 。 例如對于樣例數(shù)據(jù)： 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； 有了以上的基礎(chǔ)，我們便可以通過圖示描述解題過程，見圖 12。 我們把將段設(shè)為頂點，所在段的最大分值設(shè)為頂點的權(quán)，各頂點按自西向東的順序相 連，組成一條游覽路線。顯然，如果確定西端為起點、東段為終點，則這條游覽路線的總 分值最大。 問題是某些段的最大分值可能是負(fù)值，而最優(yōu)游覽路線的起點和終點任意，在這種情 況下，上述游覽路線就不一定最佳了。因此，我們只能枚舉這條游覽路線的所有可能的子 路線，從中找出一條子路線 I?I+1?……?J（1 ≦ I Best then Best := Sum; end 顯然，這個算法的時間復(fù)雜度為 O（N 2） 。而 N 在 1~xx1 之間，時間復(fù)雜度比較高。于 是，我們必須對這個算法進行優(yōu)化。 仍然從頂點 1 開始枚舉最優(yōu)路線。若當(dāng)前子路線延伸至頂點 I 時發(fā)現(xiàn)總分值 Sum≦0， 則應(yīng)放棄當(dāng)前子路線。因為無論 LI+1為何值，當(dāng)前子路線延伸至頂點 I+1 后的總分值不會 大于 LI+1。因此應(yīng)該從頂點 I+1 開始重新考慮新的一條子路線。通過這種優(yōu)化，可以使得 算法的時間復(fù)雜度降到了 O（N） 。 優(yōu)化后的算法描述如下: Best := 0; Sum := 0; for I := 1 to N – 1 do begin Sum := Sum + LI; if Sum > Best then Best := Sum; if Sum 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; {當(dāng)前游覽路線的總分值} begin {最佳游覽路線的總分值和當(dāng)前游覽路線的總分值初始化} Best := 0; Sum := 0; for I := 1 to N - 1 do begin {順序枚舉游覽路線的總分值} Inc(Sum, Score[I]); {統(tǒng)計當(dāng)前游覽路線的總分值} if Sum > Best then Best := Sum; {若當(dāng)前最佳，則記下} if Sum < 0 then Sum := 0; {若總分值<0，則考慮一條新路線} end; end; begin Init; {輸入數(shù)據(jù)} Main; {主過程} Out; {輸出} end.