全國青少年信息學(xué)奧林匹克聯(lián)賽教案動態(tài)實例分析及程序?qū)崿F(xiàn)

青少年信息學(xué)聯(lián)賽動態(tài)規(guī)劃實例分析及程序?qū)嵰?、?shù)字三角（圖３.１－１）示出了一個數(shù)字三角形。請編一個程序計算從頂至底的某處徑，使該路徑所經(jīng)過的數(shù)字的總和最大每一步可沿左斜線向下或右斜線向下走1三角形中的數(shù)字為整數(shù)INPUT.TXT573812744526７ （二、算法分如果得到一條由頂至底的某處的一條最佳路徑，那么對于該路徑上的每一個中間點來說，由頂至該中間點的路徑所經(jīng)過的數(shù)字和也為最大。因此該題是一個典型n,則可把問題看作一個n-1個階段的決策問題。從始點出發(fā)，依順向求出第一階段、第二階段，……，第n1徑。設(shè)ｆk（Ｕk）━━從第ｋ階段中的點Ｕk至三角形頂點有一條最佳路徑，該路徑Ｕk1━━ｋ－１階段中某點Ｕk沿左斜線向下的點；Ｕk2━━ｋ－１階段中某點Ｕkｄk（Ｕk1）━━ｋ階段中Ｕk1的數(shù)字；ｄk（Ｕk2）━━ｋ階段中Ｕk2的數(shù)字；ｆk（Ｕk）＝ｍａｘ｛ｆk-1（Ｕk）＋ｄk（Ｕk1），ｆk-k2）｝經(jīng)過一次順推，便可分別求出由頂至底Ｎ個數(shù)的Ｎ條路徑，在這Ｎ條路徑所經(jīng)過的Ｎ個ProgramNode=Val,Tot:[1,1ListArray[1..Maxn,1..Maxn]ofNode;算表N,Max,{行數(shù),最大總和}I,JInteger;變量Fi:Text;{文件變量}ProcedureInit;Assign(Fi,'INPUT.TXTReset(Fi);{文件讀準(zhǔn)備}Readln(Fi,N);Fori1toNDo入三角形各格的數(shù)字Forj:=1toiDoRead(Fi,List[i,j].Val);End;ProcedureList[1,1].TotList[1,1].Val;從[1,1]位置開始往下順推}Fori:=2toNDoForj:=1toiDoList[i,j].Tot-1;從[1,1]至[i,j]的數(shù)字和初始化If(j<>1)(List[i-1,j-1].Tot+List[i,j].Val>List[i,j].Tot)List[i,j].Tot:=List[i-1,j-1].Tot+List[i,i-1,j-1]選擇右斜線向下會使[1,1]至[i,j]If(j<>i)(List[i-1,j].Tot+List[i,j].Val>List[i,j].Tot)List[i,j].Tot:=List[i-1,j].Tot+List[i,i-1,j]選擇左斜線向下會使[1,1]至[i,jEnd;{for}Max:=[1,1]NFori:=2toNDoIfList[N,i].Tot>List[N,Max].TotThenMax:=i; n(List[N,Max].Tot)End;{main}Init;Main{求最大總和}二、Problem:打鼴Contents:n*nm機器人每次只能向前后左右移動一個格子，問最多機器人能打多少鼴鼠？(n<=1000, Difficulty:Source:HNOI2004_day_*_*Solution:記得學(xué)OI不到幾個月，高一剛上來就做的這道題..著實郁悶了半天,有一個思路1000*1000的數(shù)組亂搞…忘了可以過幾個來著..又翻到這道題的時候是2月份了..發(fā)現(xiàn)f[i]表示：如果機器人最后的老鼠是第i只，這種情況下機器人最多可以多少老鼠。就可以了,然后我赫然發(fā)10^8div2TLE鑒于這道題郁悶的理論時間復(fù)雜度無法優(yōu)化，我請教了朱老師，原來動態(tài)規(guī)劃枚舉順序也有其優(yōu)化技巧，由于思路不是自己的，僅作簡要介紹：(1).將更快、更容易“短路”的判斷放(2).將內(nèi)部循環(huán)（j的循環(huán)）倒序，近最優(yōu)總分=第一題 得分=100.0用時=mole-====mole-====mole-====mole-====mole-====mole-====mole-====mole-====mole-====mole-====iTi(xi,yi)，T1<=T2<=T3<=…<=Tm假設(shè)機器人了L只老鼠，不妨設(shè)這些老鼠的編號是a1,a2,…,aL。顯然對于i(1<=i<=L-1T[ai+1]-T[ai]>=|x[ai+1]-x[ai]|+|y[ai+1]-y[ai]|。f[i]表示：如果機器人最后的老鼠是第i只，這種情況下機器人最多可以多f[i]=max{f[j]+1,1<=j<i,T[i]-T[j]>=|xi-xj|+|yi-我們的代碼：fori:=1tomdof[i]:=forj:=1toi–1if(abs(x[i]-x[j])+abs(y[i]-y[j])<=T[i]-T[j])and(f[j]>f[i])thenf[i]:=f[j];它無疑是正確的。但是循環(huán)中的判斷語句大有文章可做：上面的代碼每次都鐵定至321以我們可以將(f[j]>f[i])if(f[j]>f[i])and(abs(x[i]-x[j])+abs(y[i]-y[j])<=T[i]-T[j])這樣做的好處是一旦f[j]<=f[i]就可以執(zhí)行“短路操作”（也就是說后面那一大截1second訴我們，機器人一般情況下不可能打完一只老鼠之后就跑到很遠(yuǎn)的地方去尋找新的獵物，肯定是一碰到一點老鼠就打一點。所以機器人相繼打的兩只老鼠的出現(xiàn)時間不可能相差太遠(yuǎn)。因此在方程f[i]=max{f[j]+1,1<=j<i,T[i]-T[j]>=|xi-xj|+|yi-if(f[j]>f[i])and(abs(x[i]-x[j])+abs(y[i]-y[j])<=T[i]-T[j])f[i]越早接近最優(yōu)值，判斷語句的效率就越高（因為后面一截可以被短路掉）。因此循環(huán)語句改成這樣的形式：fori:=1tomdobeginf[i]:=0;forj:=i–1downto1if(f[j]>f[i])and(abs(x[i]-x[j])+abs(y[i]-y[j])<=T[i]-T[j])thenf[i]:=f[j];Programvarf,t,x,y:array[1..10000]oflongint;i,j,m,n,ans:longint; fori:=1tomdoreadln(t[i],x[i],y[i]);fori:=1tomdoforj:=i-1downto1if(f[j]>f[i])and(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j])theniff[i]>ansthenans:=f[i];assign(output,'mole.out');rewrite(output);三、最大連續(xù)子序給出一個長度為n的整數(shù)序列A，找出i,j使得那一段連續(xù)數(shù)之和最大。第一行為n二行為數(shù)列63-524-1FiAiFi=max{Fi-Programzuidalianxuzixulie;a,s:array[0..10000]ofinteger;fori:=1tondos[i]:=s[i-1]+a[i];fori:=1tondoforj:=1tonifs[j]-s[i]>maxthenmax:=s[j]-s[i];四、街道問這是一道簡單而又典型的動態(tài)規(guī)劃題，許多介紹動態(tài)規(guī)劃的書與文章中都拿它來做例子。通常，書上的解答是這樣的：kk前處于這一階段上的哪一點。這時的模型實際上已經(jīng)轉(zhuǎn)化成了一個特殊的多段圖。uk=0，uk=1我們看到，這個狀態(tài)轉(zhuǎn)移方程需要根據(jù)k應(yīng)的，把它代入規(guī)劃方程而付諸實現(xiàn)時，算法也很繁。因而我們在實現(xiàn)時，一般是不會這么做的，而代之以下面方法：這樣做確實要比上面的方法簡單多了，但是它已經(jīng)破壞了動態(tài)規(guī)劃的本來面目，而不存在明確的階段特征了。如果說這種方法是以地圖中的行（A、B、C、D）來劃分也許這沒什么大不了的，因為實踐比理論更有說服力。但是，如果我們把題目擴展一下：在地圖中找出從左下角到右上角的兩條路徑，兩條路徑中的任何一條邊都不能，并且要求兩條路徑的總長度最短。這時，再用這種"簡單"的方法就不太好辦了。如果非得套用這種方法的話，則最優(yōu)指標(biāo)函數(shù)就需要有的下標(biāo)，并且難以處理兩條路徑"不能"的問題。而我們回到原先"標(biāo)準(zhǔn)"的動態(tài)規(guī)劃法，就會發(fā)現(xiàn)這個問題很好解決，只需要加一維狀態(tài)變量就成了。即用xk=(ak,bk)k應(yīng)的，決策變量也增加一維，用uk=(xk,yk)分別表示兩條路徑的行走方向。狀態(tài)轉(zhuǎn)移時將兩條路徑分別考慮在寫規(guī)劃方程時，只要對兩條路徑走到同一個點的情況稍微處理一下，減少可選的決策個數(shù)：六、花店櫥假設(shè)你想以最美觀的方式布置花店的櫥窗。現(xiàn)在你有F1V，VV1FI＜IJ1，2，一束康乃馨的在秋海棠左邊的花瓶中，秋海棠必須放在康乃馨左邊的花瓶中。如果花瓶的數(shù)目大每一個花瓶都具有各自的特點。因此，當(dāng)各個花瓶中放入不同的花束時，會產(chǎn)生不同的美學(xué)效果，并以美學(xué)值（一個整數(shù)）來表示，空置花瓶的美學(xué)值為零。 1234517--25-3-5--例如，根據(jù)上表，杜鵑花放在2會顯得非常好看；但若放在花4為取得最佳美學(xué)效果，你必須在保持花束順序的前提下，使花束的擺放取得最大的美學(xué)值。如果有不止一種的擺放方式具有最大的美學(xué)值，則其中任何一直擺放方式都可以接受，但你只要輸出任意一種擺放方式。1≤F≤100，F(xiàn)1F。F≤V≤100，V-50≤Aij≤50，Aijij隨后的FV，Aij（i+1）j12】35 23-5- 21- -21 -4- 12】IOI99有序，因此我們一眼便可看出這題應(yīng)該用動態(tài)規(guī)劃來解決。但是，如何動態(tài)規(guī)劃呢？如何劃分階段，又如何選擇狀態(tài)呢？<方法以花束的編號來劃分階段。在這里，第k階段布置第k束花，共有F束花，有F+1個階段，增加第F+1階段是為了計算的方便；狀態(tài)變量xk表示第k束花所在的花瓶。而對于每一個狀態(tài)xk，決策uk就是第k+1束花放置的花瓶號；最優(yōu)指標(biāo)函數(shù)fk(xk)表示從第k束花到第n束花所得到的最大美學(xué)值；A(i,j)是花束i插在花瓶j中的美學(xué)值,V,F狀態(tài)轉(zhuǎn)移方程為,方法1的規(guī)劃方程中的允許決策空間：xk+1≤uk≤V-(F-k)+1比較麻煩，因此有待改進。還是以花束的編號來劃分階段，第k階段布置第k束花；狀態(tài)變量xk表示第k束花所在的花瓶；注意，這里我們考慮倒過來布置花瓶，即從第F束花開始布置到第1束花。于是狀態(tài)變量uk表示第k-1束花所在的花瓶；最優(yōu)指標(biāo)fk(xk)表示從第一束花到第k束花所獲得的美學(xué)價值；A(i,j)是花束i插在花瓶j中的美學(xué)值,V是花瓶總數(shù),F可以看出，這種方法實質(zhì)上和方法1沒有區(qū)別，但是允許決策空間的表示變得簡單<方法以花瓶的數(shù)目來劃分階段，第k個階段決定花瓶k中是否放花；狀態(tài)變量xk表示前個花瓶中，用變量uk=10來表示。最優(yōu)指標(biāo)函數(shù)fk(xk)表示前k個花瓶中插了xk三種不同的方法都成功地解決了問題，只不過因為階段的劃分不同，狀態(tài)的表示不同，決策的選擇有多有少，所以算法的時間復(fù)雜度也就不同。這個例子具有很大的普遍性。有很多的多階段決策問題都有著不止一種的階段劃分方法，因而往往就有不止一種的規(guī)劃方法。有時各種方法所產(chǎn)生的效果是差不多的，但的時候，就像我們的例子一樣，兩種方在某個方面有些區(qū)別。所以，在用動態(tài)規(guī)劃解題的時候，可以多想是否有其它的解法。對于不同的解法，要注意比較，好的算法好在哪里，差一點的算法差在哪里。從各種不同算法的比較中，我們可以更深刻地動態(tài)規(guī)劃的構(gòu)思技巧。七、航線設(shè)N假如你是一個才華橫溢的設(shè)計師,該如何設(shè)置友好城市間的航線使的航線數(shù)又最大又不相交呢?programdongtai; d:array[1..1000,1..4]ofinteger;procedureprint(L:integer); n(',k);wrin(d[L,1]:4,d[L,2]:4);{輸出可以設(shè)置航線的友好城市代碼}untiLL=0 n( n('輸入友好城市對（fori:=1tono fori:=1tondo fori:=n-1downto1do L:=0;p:=0;{L，Pforj:=i+1tondo if(d[i,2]L)I面城市的終點（即不相交 {并且此 {那么L等于城市J的可以設(shè)置航線數(shù)} ifL>0then 1} k:=d[1,3];{K fori:=2tondoK，同時Lifd[i,3]>kthenfori:=1tondo Kifd[i,3]=kthen八、最長不降子序 i1<i2<i3<…<iea(i1)<a(i2)<…<a(iee10，12，16，2461·a(na(n)2·a(n-1a(n-1)>a(n)1a(n-1a(n)。3·a(i)開始，此時最長不下降序列應(yīng)該按下列方法求出:(3):（逆推法programli1;constmaxn=100;vara,b,c:array[1..maxn]ofinteger;fori:=1tondo;fori:=n-1downto1doforj:=i+1tonif(a[i]<a[j])and(b[j]>max)then beginmax:=b[j];p:=jend;ifp<>0thenbeginb[i]:=b[p]+1;c[i]:=pendfori:=1tonifb[i]>maxthenbeginmax:=b[i];p:=iend;write('resultis:');whilep<>0dobeginwrite(a[p]:5);p:=c[p]end;包問一個旅行者有一個最多能用m公斤的背包，現(xiàn)在有n種物品，它們的總重量分別是 2.0/1一個旅行者有一個最多能用m公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1，W2，...,Wn,它們的價值分別為C1.若每種物品只有一件求旅行者能獲得nO（2n）。按設(shè)f(i，xixf（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））f（n，m）f（0，x）＝0，f(i,0)=0;programknapsack02;constmaxm=200;maxn=30;typear=array[1..maxn]ofinteger;varm,n,j,i:integer;f:array[0..maxn,0..maxm]ofinteger;functionmax(x,y:integer):integer;ifx>ythenmax:=xelsemax:=y;fori:=1tondofori:=1tomdof(0,i):=0;fori:=1tondof(i,0):=0;fori:=1tondoforj:=1tomdoifj>=w[i]thenf[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])elsef[i,j]:=f[i-1,j];使用二維數(shù)組各子問題時方便，但當(dāng)maxm較大時如maxn=2000時不能定義二維f,j:=1tomj:=mdownto一個旅行者有一