【正文】 end.運(yùn)用動(dòng)態(tài)規(guī)劃法求解問(wèn)題的關(guān)鍵是找出狀態(tài)轉(zhuǎn)移方程，只要找出了狀態(tài)轉(zhuǎn)移方程，問(wèn)題就解決了一半，剩下的事情就是解決如何把狀態(tài)轉(zhuǎn)移方程用程序?qū)崿F(xiàn)。 writeln(nmax+1)。)。 {枚舉中間最高的} assign(output,39。 {從右到左求最大下降子序列} end。 for i:=2 to n do for j:=1 to i1 do begin if (t[i]t[j])and(f1[j]=f1[i]) then f1[i]:=f1[j]+1。{for} close(input)。f2[i]:=1。 for i:=1 to n do begin read(t[i])。 reset(input)。39。 i,j,n,max:integer。有了狀態(tài)轉(zhuǎn)移方程，程序?qū)崿F(xiàn)就非常容易了。這樣就得到狀態(tài)轉(zhuǎn)移方程：f1(i)=max{f1(j)+1} (ji,TjTi)邊界條件：f1(1)=1。我們先考慮如何求最大上升子序列的長(zhǎng)度，設(shè)f1(i)為前i個(gè)同學(xué)的最大上升子序列長(zhǎng)度。先分別從左到右求最大上升子序列，從右到左求最大下降子序列，再枚舉中間最高的一個(gè)人。【輸出文件】，這一行只包含一個(gè)整數(shù)，就是最少需要幾位同學(xué)出列。【輸入文件】（2 = N = 100），表示同學(xué)的總數(shù)。合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1, 2, …, K，他們的身高分別為T1, T2, …, TK，則他們的身高滿足T1 T2 … Ti , Ti Ti+1 … TK (1 = i = K)。根據(jù)以上的步驟設(shè)計(jì)，可以得到動(dòng)態(tài)規(guī)劃設(shè)計(jì)的一般模式：for k:=階段最小值to 階段最大值do {順推每一個(gè)階段} for I:=狀態(tài)最小值to 狀態(tài)最大值do {枚舉階段k的每一個(gè)狀態(tài)} for j:=決策最小值to 決策最大值do {枚舉階段k中狀態(tài)i可選擇的每一種決策}f[ik]:=min（max）{f[ik1]+a[ik1，jk1]|ik1通過(guò)決策jk1可達(dá)ik} 有了以上的設(shè)計(jì)模式，對(duì)于簡(jiǎn)單的動(dòng)態(tài)規(guī)劃問(wèn)題，就可以按部就班地進(jìn)行動(dòng)態(tài)規(guī)劃設(shè)計(jì)。 尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一個(gè)遞推的終止條件或邊界條件。確定狀態(tài)：將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處的各種客觀情況用不同的狀態(tài)表示出來(lái)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過(guò)程的一條活動(dòng)路線。 各階段狀態(tài)之間的轉(zhuǎn)換有明確定義的費(fèi)用，而且在選擇最佳決策時(shí)有遞推關(guān)系（即動(dòng)態(tài)轉(zhuǎn)移方程）。 每個(gè)階段有若干個(gè)可能狀態(tài) 一個(gè)決策將你從一個(gè)階段的一種狀態(tài)帶到下一個(gè)階段的某種狀態(tài)。動(dòng)態(tài)規(guī)劃法的定義：在求解問(wèn)題中，對(duì)于每一步?jīng)Q策，列出各種可能的局部解，再依據(jù)某種判定條件，舍棄那些肯定不能得到最優(yōu)解的局部解，在每一步都經(jīng)過(guò)篩選，以每一步都是最優(yōu)解來(lái)保證全局是最優(yōu)解，這種求解方法稱為動(dòng)態(tài)規(guī)劃法。 決策：從某階段的一個(gè)狀態(tài)演變到下一個(gè)階段某狀態(tài)的選擇。算法在信息學(xué)奧賽中的應(yīng)用（動(dòng)態(tài)規(guī)劃法）在學(xué)習(xí)動(dòng)態(tài)規(guī)劃法之前，我們先來(lái)了解動(dòng)態(tài)規(guī)劃的幾個(gè)概念 階段：把問(wèn)題分成幾個(gè)相互聯(lián)系的有順序的幾個(gè)環(huán)節(jié)，這些環(huán)節(jié)即稱為階段。)END.兩種搜索算法的比較：搜索方式擴(kuò)展方式數(shù)據(jù)結(jié)構(gòu)適合求解的問(wèn)題深度優(yōu)先后產(chǎn)生先擴(kuò)展?？尚薪饣蛩薪鈴V度優(yōu)先先產(chǎn)生先擴(kuò)展隊(duì)列最優(yōu)解在選擇搜索方式時(shí)，并不是完全遵循以上原則，具體還是要根據(jù)題目的要求而定。writeln(39。BEGIN init。 until(op[0]=cl[0])or(a[cl[0]]^.x5)or(op[1]=cl[1])or (a[cl[1]]^.x5)。{for} repeat if (op[0]cl[0])and(a[cl[0]]^.x=5)then expand(0,0)。 a[cl[st]]^.x:=0。 new(a[cl[st]])。 op[st]:=be+0。var be,k,st:integer。{for}end。{if} end。 check(be,st)。{if} a[cl[st]]^.s:= copy(d,1,j1)+ x[i,1st]+ copy(d,j+lx,ld)。 new(a[cl[st]])。 for i:=1 to mark do begin lx:=length(x[i,st])。 k:=a[op[st]]^.x。begin inc(op[st])。 {擴(kuò)展產(chǎn)生新節(jié)點(diǎn)}procedure expand(be,st:integer)。 bool(be,st)。exit。{判斷節(jié)點(diǎn)是否與前面的結(jié)點(diǎn)重復(fù)}procedure check(be,st:integer)。 end。begin for i:=midbe+1 to cl[1st] do if a[cl[st]]^.s=a[i]^.s then begin writeln(a[cl[st]]^.x+a[i]^.x)。end。{while} mark:=i1。 inc(i)。 39。,t)1)。 x[i,0]:=copy(t,1,pos(39。i:=0。 assign(f,fil)。t:string。procedure Init。 d,fil:string。 a:array [1..max]of ^node。end。type node=record s:string。源程序：const mid=12000。采用雙向搜索，存儲(chǔ)的結(jié)點(diǎn)數(shù)還有可能超限，我們?cè)谇跋蛩阉麝?duì)列中存儲(chǔ)5步內(nèi)變換的結(jié)點(diǎn)，在后向搜索隊(duì)列中，由于第5步產(chǎn)生的結(jié)點(diǎn)只是用來(lái)與前向隊(duì)列中的結(jié)點(diǎn)比較，所以可以不存儲(chǔ)在隊(duì)列中，后向搜索隊(duì)列只需存儲(chǔ)4步內(nèi)的結(jié)點(diǎn)，這樣就解決了存儲(chǔ)空間問(wèn)題。[輸出]:輸出至屏幕。 | 變換規(guī)則　　... ... /[輸入]:鍵盤輸人文件名。xyz39。abcd39。廣度優(yōu)先算法應(yīng)用例 字串變換（NOIP2002tg）[問(wèn)題描述]:已知有兩個(gè)字串 A$, B$ 及一組字串變換的規(guī)則（至多6個(gè)規(guī)則）:A1$ B1$　A2$ B2$ 規(guī)則的含義為：在 A$中的子串 A1$ 可以變換為 B1$、A2$ 可以變換為 B2$ …。{隊(duì)列為空}使用廣度優(yōu)先搜索時(shí)，離根結(jié)點(diǎn)最近的結(jié)點(diǎn)先擴(kuò)展，所以廣度優(yōu)先搜索法比較適合求步數(shù)最少的解，由于深度優(yōu)先使用了標(biāo)志法，使得存儲(chǔ)空間大大減少，而廣度優(yōu)先要保留所有搜索過(guò)的節(jié)點(diǎn)，隨著搜索程度的加深，所需的存儲(chǔ)空間成指數(shù)增加。 end{for}。repeatclosed 增1，取出closed所指結(jié)點(diǎn)進(jìn)行擴(kuò)展； for i:=1 to r do begin if 子結(jié)點(diǎn)符合條件then begin open增1，并把新結(jié)點(diǎn)存入數(shù)據(jù)庫(kù)隊(duì)尾；if新結(jié)點(diǎn)與原有結(jié)點(diǎn)有重復(fù) then 刪于該結(jié)點(diǎn)(open減1)else if 新結(jié)點(diǎn)即目標(biāo) then 輸出并退出 。設(shè)隊(duì)列首指針closed:=0。廣度優(yōu)先搜索基本算法：program bfs。在下一篇中將繼續(xù)介紹另一種搜索方法——廣度優(yōu)先搜索法。end.從上面的兩個(gè)例子我們可以看出，用遞歸實(shí)現(xiàn)深度優(yōu)先搜索比非遞歸更加方便。 dfs(1,1)。 ans:=0。begin readln(n,k)。{入棧} if i=k then prime(s) else dfs(i+1,j+1)。{搜索第i個(gè)數(shù)， }var j:byte。 if sqr(i)s then inc(ans){若為素?cái)?shù)則總數(shù)加1}end。begin i:=2。procedure prime(s:longint)。 ans,s:longint。為了避免不必要的搜索，程序?qū)λ阉鬟^(guò)程進(jìn)行了優(yōu)化，限制搜索范圍，在搜索過(guò)程dfs(i,m)中，參數(shù)m為第i個(gè)數(shù)的上限，下限為nk+i。求解此題時(shí)，先用深度優(yōu)先搜索法生成k個(gè)數(shù)的組合，再判斷k個(gè)數(shù)的和是否為素?cái)?shù)，若為素?cái)?shù)則總數(shù)加1。 [輸入]：鍵盤輸入，格式為：　　n , k (1=n=20，k＜n)　　x1,x2，…,xn （1=xi=5000000）[輸出]：屏幕輸出，格式為：　　一個(gè)整數(shù)（滿足條件的種數(shù)）?，F(xiàn)在，要求你計(jì)算出和為素?cái)?shù)共有多少種。從n 個(gè)整數(shù)中任選 k 個(gè)整數(shù)相加，可分別得到一系列的和。我們?cè)倏纯戳硪粋€(gè)例子。 深度大的結(jié)點(diǎn)是后產(chǎn)生的，但先得到擴(kuò)展，即“后產(chǎn)生先擴(kuò)展”，與棧的工作原理相同，因此用堆棧作為該算法的主要數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)產(chǎn)生的結(jié)點(diǎn)。)。 writeln(39。 readln(n,m)。begin a[1].x:=1。{出棧} end。{搜索下一步} a[i].x:=0。{輸出結(jié)果并退出程序} end。)。,a[j].y,39。,a[j].x,39。 for j:=2 to i do write(39。)39。,39。(39。 a[i].y:=a[i1].y+dy[j]。var j:integer。 a:array[0..50]of map。 end。 dy:array[1..4]of integer=(1,1,2,2)。為了減少搜索次數(shù)，在馬走的過(guò)程中，判斷下一步所走的位置是否在棋盤上，如果不在棋盤上，則另選一條路徑再走。例如:輸入 N=4,M=4，輸出:路徑的格式:(1,1)(2,3)(4,4)，若不存在路徑,則輸出no算法分析：我們以44的棋盤為例進(jìn)行分析，用樹(shù)形結(jié)構(gòu)表示馬走的所有過(guò)程（如下圖），求從起點(diǎn)到終點(diǎn)的路徑,實(shí)際上就是從根結(jié)點(diǎn)開(kāi)始深度優(yōu)先搜索這棵樹(shù)。搜索算法應(yīng)用例1騎士游歷:設(shè)有一個(gè)n*m的棋盤，在棋盤上任一點(diǎn)有一個(gè)中國(guó)象棋馬,馬走的規(guī)則為: 。endfor。棧頂元素出棧（即刪去mr）。深度優(yōu)先搜索的遞歸實(shí)現(xiàn)過(guò)程：procedure dfs(i)。為了減少存儲(chǔ)空間，在深度優(yōu)先搜索中，用標(biāo)志的方法記錄訪問(wèn)過(guò)的狀態(tài)，這種處理方法使得深度優(yōu)先搜索法與回溯法沒(méi)什么區(qū)別了。算法在信息學(xué)奧賽中的應(yīng)用（搜索法一） 在這里介紹兩種基本的搜索算法：深度優(yōu)先搜索和廣度優(yōu)先搜索法，以樹(shù)的搜索為例，深度優(yōu)先搜索法是優(yōu)先擴(kuò)展尚未擴(kuò)展的且具有最大深度的結(jié)點(diǎn)；廣度優(yōu)先搜索法是在擴(kuò)展完第K層的結(jié)點(diǎn)以后才擴(kuò)展K+1層的結(jié)點(diǎn)。end.貪心算法所作的選擇可以依賴于以往所作過(guò)的選擇，但決不依賴于將來(lái)的選擇，也不依賴于子問(wèn)題的解，因此貪心算法與其它算法相比具有一定的速度優(yōu)勢(shì)。 end。 s[i]:=s[j]。 end。 for i:=1 to n do begin read(k)。i,j,k,n:longint。源程序：var s:array[1..20] of string。按這種貪心標(biāo)準(zhǔn)，我們很容易找到反例：12，121 應(yīng)該組成12121而非12112,那么是不是相互包含的時(shí)候就從小到大呢？也不一定，如：12，123 就是12312而非12112,這樣情況就有很多種了。例2 （NOIP1998tg）設(shè)有n個(gè)正整數(shù)，將他們連接成一排，組成一個(gè)最大的多位整數(shù)。二是確定了可以用貪心算法之后，如何選擇一個(gè)貪心標(biāo)準(zhǔn)，才能保證得到問(wèn)題的最優(yōu)解。我們看一個(gè)找?guī)诺睦?如果一個(gè)貨幣系統(tǒng)有3種幣值,面值分別為一角、五分和一分，求最小找?guī)艛?shù)時(shí)，可以用貪心法求解；如果將這三種幣值改為一角一分、五分和一分，就不能使用貪心法求解。{then} writeln(s)。{移牌步數(shù)計(jì)數(shù)} a[i+1]:=a[i+1]+a[i]v。 v:=v div n。 inc(v,a[i])。v:=0。reset(f)。begin readln(fil)。 f:text。v:longint。我們?cè)谝苿?dòng)過(guò)程中，只是改變了移動(dòng)的順序，而移動(dòng)的次數(shù)不變，因此此題使用貪心法是可行的。如第i堆(0in)的紙牌數(shù)a[i]不等于平均值，則移動(dòng)一次(即s加1)，分兩種情況移動(dòng)：（1） 若a[i]v，則將a[i]v張紙牌從第I堆移動(dòng)到第I+1堆；（2） 若a[i]v，則將v a[i]張紙牌從第I+1堆移動(dòng)到第I堆；為了設(shè)計(jì)的方便，我們把這兩種情況統(tǒng)一看作是將a[I]v張牌從第I堆移動(dòng)到第I+1堆；移動(dòng)后有：a[I]:=v；a[I+1]:=a[I+1]+a[I]v；在從第i+1堆中取出紙牌補(bǔ)充第i堆的過(guò)程中，可能會(huì)出現(xiàn)第i+1堆的紙牌數(shù)小于零(a[i+1]+a[i]v0 )的情況。[輸入輸出樣例]：　4　9 8 17 6屏慕顯示：3算法分析：設(shè)a[i]為第i堆紙牌的張數(shù)（0=i=n），v為均分后每堆紙牌的張數(shù)，s為最小移到次數(shù)。文件格式：N（N 堆紙牌，1 = N = 100）　　A1 A2 … An （N 堆紙牌，每堆紙牌初始數(shù)，l= Ai =10000）[輸 出]：輸出至屏幕。例如 N=4，4 堆紙牌數(shù)分別為：　　①　9?、凇??、邸?7?、堋?移動(dòng)3次可達(dá)到目的：　　從 ③ 取 4 張牌放到 ④ （9 8 13 10） 從 ③ 取 3 張牌放到 ②（9 11 10 10） 從 ② 取 1 張牌放到①（10 10 10 10）。移牌規(guī)則為：在編號(hào)為 1 堆上取的紙牌，只能移到編號(hào)為 2 的堆上；在編號(hào)為 N 的堆上取的紙牌，只能移到編號(hào)為 N1 的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。每堆上有若干張，但紙牌總數(shù)