動(dòng)態(tài)在信息學(xué)奧林匹克競(jìng)賽中應(yīng)用

動(dòng)態(tài)規(guī)劃在信息學(xué)競(jìng)賽中的應(yīng)Catcher防衛(wèi)(G這道題目一開(kāi)始我使用回溯算法,大概可以拿到1/3分吧,后來(lái)發(fā)現(xiàn)這其實(shí)是動(dòng)態(tài)規(guī)劃算法中最基礎(chǔ)的題目,用一個(gè)二維數(shù)組C[1..Max,1..2]來(lái)建立動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程(注:C[1..Max,1]表示當(dāng)前狀態(tài)最多可擊落的數(shù),C[1..Max,2]表示當(dāng)前狀態(tài)的前繼標(biāo)志):Ci=Max{C[j]+1,(j=i+1..n)},然后程序也就不示范程序programcatcher_hh;a:array[1..4000]ofinteger;{高度數(shù)組}c:array[1..4000,1..2]ofinteger; procedureassign(f,'catcher.dat');reset(f);fori:=1tonumdoprocedurework;fillchar(c,sizeof(c),0 fori:=num-1downto1don:=0;forj:=i+1tonumif(a[i]>a[j])and(max<1+c[j,1])thenbeginn:=j;max:=1+c[j,1];end;c[i,1]:=max;c[i,2]:=n;wrin;wrin('Max:',max); max:=0;n:=0;fori:=1tonumifc[i,1]>maxthenbeginmax:=c[i,1];n:=i;wrin(n,'');n:=c[n,2];untiln=0;readfile;work;Perform演出題目描述團(tuán)指揮L.Y.MHarp演出,此后的幾天里,音樂(lè)家們輸入要在這n市用1..n號(hào)1是起點(diǎn)Flute,n終點(diǎn)Harp市,接下來(lái)有n*(n-1)(2,3,...n)的航班,接下的n-1城市2(1,3,4...n)的航班,如此下去.天對(duì)應(yīng)的兩個(gè)城市的航班的價(jià)格,價(jià)格為零表示那天兩個(gè)城市之間沒(méi)有航班.例如"375080"表示第一此循環(huán).輸入文件由n=k=0輸出對(duì)每個(gè)場(chǎng)景如果樂(lè)團(tuán)可能從城市1往另一個(gè)城市,最后(經(jīng)過(guò)k)抵達(dá)城市n,則輸出這k小值.如果不可能存在這樣的巡回演出路線,輸出0.樣例輸入321303750712011001001101204607060322010樣例輸出0初看這道題,很容易便可以想到動(dòng)態(tài)規(guī)劃,因?yàn)榈趚yx-1關(guān),符合動(dòng)態(tài)規(guī)劃的無(wú)后效性原則,即只與上一個(gè)狀態(tài)相關(guān)聯(lián),而某一天x班S=C[(x-1)modm用天數(shù)和地點(diǎn)來(lái)規(guī)劃用一個(gè)數(shù)組A[1..1000,1..10]來(lái),A[i,j]表示第i天到達(dá)第j個(gè)城市的最優(yōu)值,C[i,j,l]表示i市與j城市間第l則A[i,j]=Min{A[i-1,l]+C[l,j,i](l=1..n示范程序programperform_hh;a:array[1..1000,1..10]ofinteger; c:array[1..10,1..10]ofrecord{航班價(jià)格數(shù)組}t:array[1..30]ofe:array[1..1000]ofinteger;procedurework;fori:=1tondoifthena[1,i]:=c[1,i].t[1];fori:=2tokforj:=1tondoforl:=1tondoifandc[l,j].t[(i-1mod thena[i,j]:=a[i-1,l]+c[l,j].t[(i-1)modc[l,j].num+1]; e[p]:=a[k,n];{第p優(yōu)值}procedurereadfile; assign(f,'PERFORM.DAT');reset(f);assign(fout,'PERFORM.OUT');rewrite(fout);readln(f,n,k);p:=0;while(n<>0)and(k<>0)dofori:=1tondoforj:=1toi-1doforl:=1toc[i,j].numforj:=i+1tondoforl:=1toc[i,j].numdofori:=1top-1do市息學(xué)競(jìng)中據(jù)當(dāng)要地位每省賽8題中般有2~3道目于態(tài)劃,起(書(shū)必須整本整本的抄),求一種分配方法,使抄書(shū)頁(yè)數(shù)最多的人抄書(shū)頁(yè)數(shù)盡可能少.(G''99Books).（GDKOI'2