動規(guī)狀壓dp動態(tài)history第三章程序設計

第三章動態(tài)程序設 機器分配 快餐問題 求函數(shù)最大值(CTSC'95)石子合并 游覽街區(qū) 積木游戲 免費餡餅 棋盤分割 隕石的 商店購物 最長前綴 多邊形 選課 拯救大兵 補丁VS錯誤 迷宮改造 奶牛浴場 第三章動態(tài)程序設計4-1帶權(quán)有向多段圖點要到達距離加上3或是C2到D的最短距離加上2，……。G[i]iDG[C1]=4，G[C2]=3，G[C3]=5，根據(jù)上面的分所以A到D的最短距離是10，最短路徑是A→B1→C2→D用k表示。此外，也有階段變量是連續(xù)的情形。如果過程可以在任何時刻作出決策，且在面的例子中，第一個階段就是點A，而第二個階段就是點A到點B，第三個階段是點B到點C，而第四個階段是點C到點D。狀態(tài)表示每個階段開始的自然狀況或客觀條件，它不以人們的意志為轉(zhuǎn)移，AB1B2，第三個階段是三個狀態(tài)C1，C2和C3，而第四個階段又是一個狀態(tài)D。外，狀態(tài)可以有多個分量(情形)，因而用向量來代表；而且在每個階段的狀態(tài)維數(shù)可x(k+1)x(k+1)x(k)ku(k)的值變化而變化，那么可以把這一關系看成(x(k)u(kx(k+1)確定的對應關系，用分析來具體說明這一點：從A到D，我們知道，最短路徑是A→B1→C2→D，這些點的選擇構(gòu)成了這個例子的最優(yōu)策略，根據(jù)最優(yōu)性原理，這個策略的每個子策略應是最優(yōu)：A→B1→C2是A到C2的最短路徑，B1→C2→D也是B1到D的最短路徑……事實正是如一．機器分配總公司擁有高效生產(chǎn)設備M臺，準備分給下屬的N個公司。各若獲得這些設但總臺數(shù)不得超過總設備數(shù)M。保存數(shù)據(jù)的文件名從鍵盤輸入。N。接下來是一個M*N的矩陣，表明了第I個公司分配J臺機器的表示前J臺機器的最大。則狀態(tài)轉(zhuǎn)移方程F[I，J]=Max{F[I-1，KValue[I，J-K]}（0〈=K〈=Jprogramhnoi_95_4;a,b,c :array[0..15,0..15]oflongint; :array[0..15]oflongint;n,m:longint;procedureinit; :I,j,k :integer;Assign(fi,’input.txt’);Reset(fi);ForI:=0tomdoFork:=1tondoProceduredynamic;VarI,j,k:longint;ForI:=1tonForj:=0tomdoFork:=0tojdoIfb[I-1,k]+a[I,j-k]>b[I,j]thenB[I,j]:=b[I-1,k]+a[I,j-

二．最長不下降序列b1,b2,b3,…,bm中有長度為n的不下降序列bi1,bi2,bi3,…,bin。求序列b1,b2,b3,…,bm中所nnF(iIF(iF(1)—F(I-1F(jj<Ibi>bj)，那么前IjbiF(i)=max{F(j)+1}(j<I,設Total(I)為前I個數(shù)中最長不下降序列的個數(shù)。那么，要求Total(iTotal(jj<I，bj<bij序列長度為前I個數(shù)中最大不下降序列長度+1，并把他們累加起來。即Total(i)=∑Total(j)(j<I,bj<bi,F(i)=F(j)-Total(i)(F(i)=max)的累加和即可。12212對原序列按b（當bi=bj時按F）排序，增設Order(i列中的I個數(shù)在原序列中的位置?？梢姡斍骉otal(i)時，當F(j)=F(j+1),b(j)=b(j+1)且Order(j+1)<Order(i)時，便不累加Total(j)。這樣就避免了重復。{$MProgramconst {len記錄最大長度} :array[1..maxN]ofProcedureinit; varf whilenoteoln(f)dobeginProceduremain;vari,j,torder:array[1..maxN]ofinteger;total:array[1..maxN]oflongint; fori:=2tondobeginforj:=1toi-1if(b[i]>b[j])and(f[i]<f[j]+1)theniff[i]>lenthenlen:=f[i] fori:=1tondofori:=1tondo forj:=i+1tondo fori:=1tondoiff[i]=1thentotal[i]:=1forj:=i-1downto1if(b[j+1]<>b[j])or(f[j+1]<>f[j])or(order[j+1]>=order[i])thenif(f[i]=len)and(b[i]<>b[i+1])then Procedureout;

三．凸多邊形三角劃分問如何把這個凸多邊形劃分成N-2個互不相交的三角形，使得這些三角形頂點的權(quán)的乘積輸入文件：第一行頂點數(shù)第二行N個頂點（1N）的權(quán)值122123245輸出示例：Theminimumis

Theformationof3triangle:345,153,123F[I,J]（I<J）IJ Var :Array[1..50]Of :Array[1..50,1..50]Of :Array[1..50,1..50]Of ProcedureInit; VarI ForI:=1ToNDoRead(S[I]);Procedure （動態(tài)規(guī)劃VarI,J,K ForI:=1ToNForJ:=I+1ToNDoF[I,J]:=Maxlongint;（賦初始值ForI:=N-2Downto1DoForJ:=I+2ToNDoForK:=I+1ToJ-1If(F[I,J]>F[I,K]+F[K,J]+S[I]*S[J]*S[K]) （記錄父節(jié)點ProcedurePrint(I,J:Integer);（輸出每個三角形IfJ=I+1ThenExit;Write(',',I,'',J,'',D[I,J]);ProcedureOut;（輸出信息Assign(Output,'Output.Txt');Rewrite(Output);Wrin('Theminimumis:',F[1,N]:0:0);Wrin('Theformationof',N-2,'triangle:');Write(1,'',N,''D[1,N]);Begin（主程序

四．系統(tǒng)可靠性給定一些系統(tǒng)備用件的單價Ck，以及當用Mk個此備用件時部件的正常工作概率（Mk會使得整個前I項備用件組成的系統(tǒng)可靠性比原先的更高，與原假設。所以可以證明F[I,money]:=max{F[I-1,money– }(0<=K[I]<=CdivCi{$MProgramsystem_dependability;constfinp='input.txt';varf,p:array[0..maxm]ofreal;procedureprint;varoutput:text;assign(output,fout);rewrite(output);assign(input,finp);reset(input);fori:=0tocdof[i]:=1;fori:=1tondoread(input,co);m:=cdivfore:=0tomdoread(input,p[e]);forj:=cdownto0dom:=jdivco;max:=0;fork:=0tomdoifv>maxthenmax:=v;

五．快餐問題餐由A個漢堡，B個薯條和C個飲料組成。價格便宜。為了提高產(chǎn)量，Peter從著名的麥Peter不超過100個。輸入文件共四行。第一行為三個不超過100A、B、C中間以一個空格分開。第二行為3個不超過100的正整數(shù)p1,p2,p3間以一個空格分開。第三行為N(0<=0<=10)，第四行為N個不超過10000的正整數(shù)，分22212261狀態(tài)表示：用p[I,j,k]Ij，k用r[I,j,k]表示第I條生產(chǎn)線生產(chǎn)j個漢堡，k個薯條的情況下最多可生產(chǎn)態(tài)轉(zhuǎn)移方程：p[I,j,kMax{p[I-1,j1,k1]+r[I,j-j1,k-(0<=j1<=j,0<=k1<=k,且（j-j1）*p1+(k-k1)*p2<=第I當個上限值（Min{100divA100divB100divC}）,這是一個很好的判斷條件，他可以幫我們?nèi)?、小結(jié)（1）結(jié)構(gòu)：由于每一階段狀態(tài)只與上一階段狀態(tài)有關，所以我們可以只用兩個100*100（2）4原起始值 forI:=1tondo forI:=1tondoforj:=0totot[I]divp1 forj:=0tomin(q1,tot[I]divp1)fork:=0to(tot[I]-p1*j)divp2do fork:=0tomin(q2,(tot[I]-p1*j)divp2)doforj1:=0tojdo forj1:=max(0,j-t[I]divp1)tomin(j,tot[I-1]divp1)fork1:=0tokdo fork1:=max(0,k-(t[I]-(j-j1)*p1)divp2)tomin(k,(tot[I-1]-p1*j1)divp2){注：具體變量用途請參考程 {$MprogramFastFood; = ='output2.txt'; : array[0..100,0..100of array[0..10of tot:1-I條生產(chǎn)線生產(chǎn)時間的總和} :longint; procedureinit; :reset(f);fori:=1tondoread(f,t[i]);close(f);ifn=0thenbegin {特殊情況處理}close(f); min(i,j:longint):longint; ifi>jthenmin:=jelsemin:= max(i,j:longint):longint; ifi>jthenmax:=ielsemax:=proceduremain; :longint; {q:上限值；q1,q2A,Bqmin100diva,min100divb100divcq1:=q*a;q2:=q*b;tt:=t;i:=j:=while(j>0)and(i<=n)do {用貪心法求出N（可行解）}ifj>tt[i]thenbegin tt[i]:=0;inc(i);elsebegindec(tt[i],j);j:=0;end;ifj=0thenbeginj:=while(j>0)and(i<=n)doifj>tt[i]thendec(j,tt[i]);tt[i]:=0;inc(i);elsebegindec(tt[i],j);j:=0;ifj=0thenbegin close(f);tot[0]:=fori:=1tondotot[i]:=tot[i-1]+iftot[n]div(a*p1+b*p2+c*p3)<qthenbegin q:=tot[n]div(a*p1+b*p2+c*p3);q1:=q*a;q2:=fori:=1tondoforj:=0tomin(q1,t[i]divp1)fork:=0tomin(q2,(t[i]-p1*j)divp2)dor[j,k]:=(t[i]-p1*j-p2*k)divp3; {數(shù)組}forj:=0tomin(q1,tot[i]divp1)dofork:=0tomin(q2,(tot[i]-p1*j)divp2)forj1:=max(0,j-t[i]divp1)tomin(j,tot[i-1]divp1)fork1:=max(0,k-(t[i]-(j-j1)*p1)divp2)tomin(k,(tot[i-1]-p1*j1)divp2)doifp[j,k]<pp[j1,k1]+r[j-j1,k-k1]thenp[j,k]:=pp[j1,k1]+r[j-j1,k-k1];ifp[q*a,q*b]>=q*cthenbeginclose(f);pp:=forj:=0tomin(100,tot[i]divp1)fork:=0tomin(100,(tot[i]-p1*j)divp2)doifp[j,k]>100thenp[j,k]:=100;{outk1:=0; {輸出最優(yōu)值 forj:=0to100doif(jdiva>k1)fork:=0to100if(kdivb>k1)and(p[j,k]divc>k1)k1:=min(min(jdiva,kdivb),p[j,k]divcclose(f);

A,B,C0-10x,y,zA(x)+B(y)+C(z)為最大,x*x+y*y+z*z<N，N由鍵盤X012345678924755318其中 X,Y,Z,的值,具體實programCTSC_95_4; array[1..3,0..10ofinteger 7,11,13,15,18,22,18,15,(5,10,15,20,24,18, (8,12,17,22,19,16,14, :array[1..3,0..300]of {狀態(tài)S[I,JIjpre:array[1..3,0..300]ofinteger; :longint;proceduremain;i,j,k,p,x,y,z:integer; ifn>301then )則fori:=0to10dos[1,i*i]:=f[1,i];fori:=1to2doforj:=0ton-1doifs[i,j]>s[i+1,j]begins[i+1,j]:=s[i,j];pre[i+1,j]:=j;end;fork:=0to10doifs[i,j]+f[i+1,k]>s[i+1,j+k*k]thenbeginp:=j+k*k;ifp>=nthenbreak;pre[i+1,p]:=j;s[i+1,p]:=s[i,j]+f[i+1,k];p:=0;k:=fori:=0ton-1ifs[3,i]>kthenbegink:=s[3,i];p:=i;ztrunc(sqrt(p-pre[3,pp y:=trunc(sqrt(p-pre[2,p]));p:=pre[2,p]; Y}x:=trunc(sqrt(p));{求出X}

七．石子合并在一園形操場四周擺放N堆石子(N≤100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次44594459選擇一種合并石子的方案,使得做N-14458544585944輸出數(shù)據(jù):1NN+1N+22N+1每種合并方案用N行表示,其中第i1≤i≤Ni鐘次序輸出,哪一堆先輸出均可).要求將待合并的兩堆石子數(shù)以相應的負數(shù)表示,以便識別,參見MODEL2.TXT4459-459--8-5-9--4-5-94-14--4- 346542。3465546554第一34655465549第三次99152415

497313247313

6542得分5426data[I,j]i顆石子開始的接下來j顆石子合并所得的分值，max[i,j]表示將從第i顆石子開始的接下來j顆石子合并可能的最大值，那么：max[I,j]max(max[i,k]max[ik,j–k]data[I,k]data[Ik,j–k])max[i,1]=min[i,j]ij顆石子合并所得的最min[I,j]=min(min[i,k]+min[i+k,j–k]+data[I,k]+data[I+k,jk])min[I,0]=O(n2O(n2)

八．游覽街區(qū)林上可以從南向北走，也可從北向南走。北--------------南100*20001來不是很好。于是問題轉(zhuǎn)化以下：向的移動而選擇分度值最大的格線(分值為17)。對于這一點的證明如下：P(I,j)—P(I,j+1P(I,k)—P(Ik+1PIj)時，必可通過南北向移動修改P(I,j)——>P(I,k+1)—>P(I,j+1)而得到一條新路經(jīng)比原F(iI由題可知，最大分值即為：G(iIG(I-1)>0G(iG(I-1)基礎上添邊界為{$MProgramconst :array[1..maxN]ofshortint; {記錄F表} :array[1..40960]ofchar; procedureinit; vari,j fori:=1tomdobeginforj:=1ton-1dobeginifx>map[j]thenmap[j]:=xproceduremain;vart fori:=1ton-1doifs+map[i]>map[i]thenelse ifs>tthen ?procedureout;

九．積木游戲N1，2，…，NI塊積木通過同一頂點三條邊的長度分別為ai,bi,ci（i=1,2,…,N，如圖1所示：1N塊積木中選出若干塊，并將他們摞成M（1<=M<=N）1,2,…,Mk根柱子的任意一塊積木的編號都必須大于第K-1根柱子任意一塊積木（2<=K<=M2（m>=n（x>=yM根柱子的高度之和最大。NM（1<=MN<=100）,分別表示積木總數(shù)和要求摞到（1）（2）（3）I前I-1塊積木，與后面的積木無關。以任意翻轉(zhuǎn)，因此它的上表面有三種情況，對應的三個面的長和寬分別為：a和b,a和c,b和c.。設（1）f[I,j,k]表示以第I塊積木的第k面為第j根柱子的頂面的最優(yōu)方案的高度總合； （2）block[I,k]記錄每個積木的三條邊信息（block[I,4]:=block[I,1];block[I,5]:=block[I,]。其中block[I,j+2]表示當把第I塊積木的第j面朝上時所對應的高，即所增加的高度（3can[I,k,p,kc]表示第I塊積木以其第k面朝上，第p塊積木以第kc面朝上時，能否將積木I放在積木p的上面。1表示能，0表示不能。對于f[i,j,k],有兩種可能（1）除去第I塊積木，第j根柱子的最上面的積木為編號為p的，若第p塊積木以第can[I,k,,kc]=1（2）第I塊積木是第j根柱子的第一塊積木，第j-1根柱子的最上面為第p塊積木，則此時第pmax{f[p,j,kc]block[i,j2]}(1pi1,1kcf[i,j,k]

且can[ik,pkc

max{f[p,j1,kc]block[i,j2]}(1pi1,1kcf[1,1,1]:=block[1,1,3];f[1,1,2]:=block[1,1,4];f[1,1,3]:=block[1,1,5];f[I,0,k]:=0;(1<=I<=n,1<=k<=3);此算法主要需要block，can和f數(shù)組，分別需要O(n),O(n^2)和O(n*m)，總和約為120K。時間復雜度為O(n^2*m),約為10^6.{$Mprogramlcy; = = = = =array[1..maxn,1..3]of =array[0..maxm,1..3]of : : :array[1..maxn,1..3]of :array[1..maxn,1..5]of :array[1..maxn]ofproceduresort(w:byte); : :fori:=1to2doforj:=i+1to3doifblock[w,j]<block[w,p]thenp:=j;tmp:=block[w,i];block[w,i]:=block[w,p];block[w,p]:=tmp;procedureinit; :assign(fi,name1);reset(fi);assign(fo,name2);rewrite(fo);fori:=1tondo block[i,4]:=block[i,1];block[i,5]:=block[i,2];procedurecal_can; :fori:=1tondoforj:=1to3dofori:=2tondofork:=1to3doforj:=1toi-1doforp:=1to3doif(block[i,k]<=block[j,p])and(block[i,k+1]<=block[j,p+1])thenprocedurework; :cal_can;（canfori:=1tondofori:=1to3dofori:=2tondoifi>mthenup:=melseifm+i-n<1thendown:=1elsedown:=m+i-n;forj:=downtoupdofork:=1to3forq:=1toi-1doforp:=1to3doif(can[i,k]^[q,p]=1)and(f[q]^[j,p]<>0)(f[q]^[j,p]+block[i,k+2]>f[i]^[j,kthen（第一種可能if(f[q]^[j-1,p]<>0)

procedureout; : :fori:=1to3doiff[n]^[m,i]>maxthenmax:=f[n]^[m,i];

十．免費餡餅始時，游戲者站在舞臺的正，手里拿著一個托盤（如圖一。8-308（1~99之間的奇數(shù)）H（1~100之間的整數(shù)示了餡餅的初始下落時刻（0~1000秒位置、下落速度（1~100）以及分值。游戲開始時刻為0。從1開始自左向右依次對水平方向的每格編號。示向右移動一步或兩步、-1或-2表示向坐移動一步或兩步。輸出應持續(xù)到游戲者收集完F[I,J]I秒，這時游戲者站在第J列時所能得到的最大分值。那么F[I,J]=Max{F[I-1,K]}+餡餅的分 (J-2<=K<=J+2{$MProgramType =Array[1..99]Of =Array[1..99]Of =Array[1..99]OfLongint;Var :Array[1..1100]Of :Array[1..1100]Of ProcedureInit;VarU,V,W,N Assign(Input,'Input.txt');Reset(Input);Last[WiDivForU:=1To100DoBeginWhile(U=I)Or(U=0)DoIf(H-1)DivW=(H-1)/WThenBeginInc(A[U+(H-1)DivW]^[V],N);IfU+(H-1)DivW>MaxThenMax:=U+(H-1)DivW;IfSeekEof(Input)ThenBreak;ForJ:=1ToWiDoBeginForK:=-2To2If(J-K>0)And(J-K<=Wi)IfLast[J-K]>Now[J]ThenBeginIfNow[J]>-1ThenBeginIfNow[J]>SThenBeginUntil(I>Max)AndSeekeof(Input);ProcedureOut(T,M ThenOut(T-1,M- Assign(Output,'Output.txt');Rewrite(Output);

十一。棋盤分割n塊矩形棋盤。(每次切割都只能沿著棋盤格子的邊進行) 要把棋盤按上述規(guī)則分割成n塊矩形棋盤，并使各矩形棋盤總分的均方差最小。均方差，其中平均值，xi為第i塊矩形棋盤的總分。請編程對給出的棋盤及n，求出的最小值。1n(1<n<15)298100的非負整數(shù)，表示棋盤上相應格子的分值。每行31111111111111111111111111111111111111111111110首先須明確幾個條件（關鍵字，這樣對我們理解題意進而采取正確的算法解（Xi-X）的和的值作為參數(shù)，以此簡化程序的計算及的空間不難發(fā)現(xiàn)本題符合最優(yōu)化原理：即若第i次分割為最佳分割，則第i-1次分割為且必為最佳；定義函數(shù)F[i,j][i’,j’]為[i,j]、[i’,j’]分別為左上、右下角的棋盤的最優(yōu)值，F(xiàn)0[i,j][i’,j’]為[i,j]、[i’,j’]分別為左上、右下角的棋盤值，探尋函數(shù)F[i,j][i’,j’]的動態(tài)轉(zhuǎn)移方程。（圖ii-11（圖ii-11（圖ii-11（圖ii-11（圖A3=F0[i1,j1][i2,j’]+Fkkk-1每做完第k次對棋盤的規(guī)劃F0F。由此節(jié)省下許多空間。F0并統(tǒng)計出棋盤每個格子值之和fori:=1to8forj:=1to8doread(f[i,j][i,j]);ss+f[i,j][i,j];{讀入棋盤每個格子的值，并統(tǒng)計其和}fori1:=1toido {枚舉左上方坐標i1,j1}forj1:=1tojfori2:=ito8forj2:=jto8do {枚舉右上方坐標i2,j2} (i1<>i)or(j1<>j)or(i2<>i)or(j2<>j)theF0[i1,j1][i2,j2]的值，此處不再贅述。fori:=2tondobegin {分階段，第ifori1:=1to8doforj1:=1to8doforj2:=j1to8dobegin fori’:=i1toi2-1do計算A1,A2；fori’:=i1toi2-1do計算A3,A4；

F0F;

十二。釘子和小球有一個三角形木板,豎直立放，上面釘著n(n+1)/2顆釘子，還有(n+1)個格子（當n=51）dd，讓一個直徑略小于d的小球中心正對著最上面的釘子在板上自由滾落，小球每碰到一個釘子都可能落向左邊或右邊（1/2），且球的中心還會正對著下一顆將要碰上的釘子。例如圖2就是小球一條可能的路徑。我們知道小球落在第i個格子中的概率pi= ，其中i為格子的編號，從左至右依次為0,1,...,n?，F(xiàn)在的問題是計算拔掉某些釘子后，小球落在編號為mpm。假定最下面一排釘子不會被拔掉。例如圖3是某些釘子被拔掉后小球一條可能的路徑。圖 圖 圖m（0<=m<=nnn行釘子的信息，每行中‘*’表示釘子還在，‘.’表示釘子被拔去，注意在這n行中空格符可能出現(xiàn)在任何位置。5*.**.******2n個小球從頂端放入，每個小球到達底部的路徑不同，求第m個格子中小球數(shù)與總數(shù)的比值。ni（1<=i<=n）i0..i-1n+1有n+1個鐵釘位置，排成n+1個格子，編號為0..n。設經(jīng)過位置（i,j）的小球個數(shù)為Pi,j，則落入格子m的小球個數(shù)為Pn1,m，問題要求的是 2

)；否則, ←2nfori←1tonforj←1tondoif位置(i,j)有釘子{Pi1,j←Pi1,j+2Pi1,j

←Pi1,j1

Pi,j2}elsePi2,j1←Pi2,j1+Pi,j22子，直至分子不能整除2。ProgramNoi99_Ball;ConstFn='Ball.In';VarTot :Array[1..50,0..50]Of :Array[1..51,0..50]of ProcedureVar Assign(F,Fn);ForI:=1TonDoBegin

IfCh<>''ThenBeginG[i,j]:=Ch;Inc(J);Until i-1ProcedureVar

IfP[N+1,M]=0ThenBeginV:=0;U:=1;EndElseWhile(Frac(V/2)<0.1)Or(Frac(V/2)>0.9)DoBeginV:=V/2;U:=U/2;

Assign(O,On);ReWrite(O);ProcedureVar

ForI:=1ToNDoTot:=Tot*2;ForI:=1ToNForJ:=0ToI-1IfG[I,J]='*'ThenBeginEnd

十三。眾所周知，我們可以通過直角坐標系把平面上的任何一個點P用一個有序數(shù)對(x,y)平面上所有整點構(gòu)成的集合記為W。1(x1,y1),P2(2,2)y2|=1否則稱P1,P2不相鄰。定義2S是WS={P1,P2,…,Pn}(n>=1)WS稱為整點集定義3SR,TSQ1,Q2,…,Qk足QiS（1<=i<=k）;Q1=R,Qk=T;Qi~Qi+1(1<=i<=k-1)QiQi+1相鄰;對于任何1<=i<j<=k有Qi≠Q(mào)j;我們則稱點RT在整點集S上連通Q1,Q2,…,QkS4VV中的任何兩個整點，V中有且僅有一條連接這兩點的道路，則V稱為單整點集。V，求出一個VB，滿足：B是V的子集B中的任何兩個整點，在B個頂點的度數(shù)還不超過4。對于這道題目的規(guī)模N不大于1000，只需要一個兩層循環(huán)就完Fori:=1tondobeging[i,0]:=0;Forj:=1tonIfabs(x[i]-x[j])+abs(y[i]-y[j])=1thenbeginInc(g[i,0]);g[i,g[i,0]]:=j;搜索圖中權(quán)值和最大的的為以Root的第Direction個孩子為根的。把搜索得到的最大 ProcedureSearch(Root,Direction:integer);Now:=g[Root,direction];{Now即為當前所在的頂點temp:=value[Now]; {保存以Now為根的的最大權(quán)值和}forp:=1tog[Now,0]doifg[Now,p]<>Rootthenbegin Search(Now,p); {搜索Now的第P個}ifF[Now,p]>0theninc(temp,F[Now,p]); iftemp>0thenF[Root,Direction]:=tempelseF[Root,Direction]:=0; 把圖中的每一個點，以及以其為根的重新搜一遍。這樣就產(chǎn)生了的子問題。同時于是我們找到實現(xiàn)動態(tài)規(guī)劃的理論基礎對于的子問題我們就只需要計算一次，SearchF[Root,Direction]數(shù)組賦初值-1。SearchF[Root,Direction]=-1則繼續(xù)。若F[Root,Direction]不為-1，則退出。Fori:=1tonForj:=1to4dof[i,j]:=-1;ans:=0;Fori:=1tondobegins:=value[i];Forj:=1tog[i,0]dobeginSearch(i,j);Iff[i,j]>0theninc(s,f[i,j]);Ifs>ansthenans:=s;O(4*N),時間復雜度由于是遞歸實現(xiàn)，比較難以分析，大概是不到或是O(N2)。program_subset;name1='input.txt';name2='output.txt';maxn=1000; :array[1..maxn,1..4]of :array[1..maxn,0..4]ofinteger; :array[1..maxn]oflongint; : :procedurevarx,y :array[1..maxn]oflongint; :integer;assign(input,name1);fillchar(x,sizeof(x),fillchar(y,sizeof(y),fori:=1tondoreadln(x[i],y[i],value[i]);fori:=1tondobeging[i,0]:=forj:=1tonifabs(x[i]-x[j])+abs(y[i]-y[j])=1thenbegininc(g[i,0]);g[i,g[i,0]]:=j;

proceduresearch(pre,direction:integer);varnow,p :integer; :longint;iff[pre,direction]<>-1then

now:=g[pre,direction];temp:=value[now];forp:=1tog[now,0]ifg[now,p]<>prethenbeginsearch(now,p);iff[now,p]>0theninc(temp,f[now,p]);iftemp>0thenf[pre,direction]:=tempelsef[pre,direction]:=0;proceduremain;vari,j: :longint;fori:=1tonforj:=1to4dof[i,j]:=-1;ans:=0;fori:=1tondobegins:=value[i];forj:=1tog[i,0]dobeginsearch(i,j);iff[i,j]>0theninc(s,f[i,j]);ifs>ansthenans:=s;procedureprint;assign(output,name2);

十四。隕石的 點。經(jīng)過一番偵察，科學家們發(fā)現(xiàn)隕石上刻有若干行密文，每一行都包含5個整數(shù)：1111006380113種運算，他定義了一種SS表達式：一個空串是SSA是SSAASSA是SSAASSA是SSASSA和B都是SSAB也是SSSS表達式。SSSS表達式ED(E D(E)D(A)

max(D(A),例如(){()}[]2

如果EAB,其中A,B是SS4L1，L2，L3，DDL1L2對[]，L3SS11380中每行的第5個數(shù)，我們稱之為“神秘數(shù)”。輸入文件個整數(shù)1118題目對于什么是SS表達式做了大量的定義，一系列的條件讓我們?nèi)鐗嬱F中。為了看清SS表達式的本質(zhì)，有必要對條件進行簡化。1SS條件3、4、5實際上對于()、[]、{}的嵌套順序做了限制，即()內(nèi)不能嵌套[]、{}，[]內(nèi)不能潛逃{}。概括起來是兩點：SS表達式中括號要配對；{}、[]（）從外到內(nèi)依次{}l1[]l2、()l3以及深度d作為狀態(tài)表示的組成部分，即用(l1,l2,l3,d)這樣一個四元組來F(l1,l2,l3,d)F(L1,L2,L3,D)表示含有不大于解F的問題，可以轉(zhuǎn)化為求解G的問題。（l1l2,l3,dG2、G3類似定義。 ()將整個表達式分成兩部分(ss1ss2)。根據(jù)乘法原理，我們只需對兩部分。因為其內(nèi)部不可再含[]{}x=0y=0ss1的深度不可超過d-1ss1的數(shù)目為G(x,y,z,d-1)=G(0,0,z,d-1)。ss2中含有l(wèi)1-x=l1個{}，l2-y=l2個[]，l3-z-1個()，深度不可超過d，ss2的數(shù)目為G(l1,l2,l3-z-1,d)。據(jù)此，我們寫出下面這個式子：lG1(l1,l2,l3,d) G(0,0,z,d1)*G(l1,l2,l3z1,dz情況二：第一位是“[”，與其配對的“]”位于第i 得得G2(l1,l2,l3,d)

G(0,y,z,d1)*G(l1,l2y1,l3z,dylzlO(n^6)情況三：第一位是“{”，與其配對的“}”位于第i

G(x,y,z,d1)*G(l1x1,l2y,l3z,dyl2,zlO(n^7)的方式，可將空間復雜度為n^3，保存也不成問題。本題的難點在于動態(tài)規(guī)劃時情況的劃program = = = :array[0..11,0..11,0..11,-1..31]ofinteger;a1,a2,a3,dep:integer;procedurecalc; :integer;d,l1,l2,l3,x,y,z:integer;fillword(f,sizeof(f)shr1,0);ford:=0todepdof[0,0,0,d]:=ford:=1todepdoforl1:=0toa1doforl2:=0toa2doforl3:=0toa3doif(l1>0)or(l2>0)or(l3>0)thenbegins:=0;forx:=0tol1-1dofory:=0tol2doforz:=0tol3s:=(s+f[x,y,z,d-1]*f[l1-x-1,l2-y,l3-z,d])modyear;fory:=0tol2-1doforz:=0tol3s:=(s+f[0,y,z,d-1]*f[l1,l2-y-1,l3-z,d])modyear;forz:=0tol3-1dos:=(s+f[0,0,z,d-1]*f[l1,l2,l3-z-1,d])modyear;f[l1,l2,l3,d]:=s;procedureinit;assign(input,finp);readln(a1,a2,a3,dep);procedureprint;left:longint;assign(output,fout);left:=f[a1,a2,a3,dep]-f[a1,a2,a3,dep-1];ifleft<0thenleft:=left+year;

十五。商店購物某商店中每種商品都有一個價格。例如，一朵花的價格是2ICU(ICU是信息學競賽的貨幣的單位）;一個花瓶的價格是5ICU。為了吸引的顧客，商店提供了特殊價5ICU2110ICU12ICU為:3朵花和2個花瓶。那么顧客應付款為14ICU因為:朵花加2個花瓶:價:10朵 正常價:4用兩個文件表示輸入數(shù)據(jù)。第一個文件INPUT．TXT描述顧客所購物品（放在購物筐中）;第二個文件描述商店提供的商品及價格（文件名為OFFER．TXT。兩個文件中B（0≤B≤5B3C，K，P。C代表商品的編碼（每種商品有一個唯一1≤C≤999件商品的價格，1≤P≤999。請注意，購物筐中最多可放5*5＝25件商品。（0≤S≤99（C，K5。本行最后一個數(shù)字P（1≤P≤9999）代表此商品組合的價。當然，價要低于55，那么用一個五元組來表示第I種商品買AI 如果我們能夠使用第I條商品組合的話，狀態(tài)就便為了：F（A1-SI1，A2-SI2，A3-SI3，A4-SI4，A5-SI5）這樣的話，狀態(tài)1的費用為狀態(tài)2的費用加上SI的費用，而狀態(tài)2F[a,b,c,d,e]=Min{F[a-S1,b-S2,c-S3,d-S4,e-S5]+SaleCostF[a,b,c,d,e]=Cost[1]*a+Cost[2]*b+Cost[3]*c+Cost[4]*d+Cost即不用的費用O（65商品總數(shù)不足5種的，可以把不買的那幾種看成是0件，以統(tǒng)一操作。program_shop;

name1='input.txt';name2='output.txt';name3='offer.txt';saletype=array[1..5]of :array[0..5,0..5,0..5,0..5,0..5]of :array[0..5]of :array[1..999]of :array[1..99]ofsaletype; :array[1..99]ofinteger; :array[1..99]ofboolean; :array[0..5]of :procedurevari,cc,kk,pp,j :word;

assign(input,name1); fillchar(f,sizeof(f),0);fillchar(code,sizeof(code),fillchar(sale,sizeof(sale),fillchar(costs,sizeof(costs),fillchar(st,sizeof(st),fillchar(ed,sizeof(ed),fillchar(check,sizeof(check),true); fori:=1tobdobeginreadln(cc,kk,pp);code[cc]:=i;ed[i]:=kk; {ed[i]表示第I種商品的數(shù)量}costs[i]:=pp;assign(input,name3); fori:=1tosdobeginforj:=1toccdobeginread(kk,pp);ifcode[kk]=0thenbegincheck[i]:=false;break;sale[i,code[kk]]:=pp;paysale[i]:=cc;proceduremain;var : :array[1..5]ofbyte; :word; :boolean;fori[1]:=st[1]toed[1]fori[2]:=st[2]toed[2]fori[3]:=st[3]toed[3]fori[4]:=st[4]toed[4]fori[5st[5toed[5do q:=forj:=1to5doinc(q,costs[j]*i[j]); forj:=1tos ifcheck[j]thenbegincan:=true;fork:=1to5ifi[ksale[j,kthencanfalseifcanthenbegint:=paysale[j]i[1]-sale[j,1],i[2]-sale[j,i[3]-sale[j,3],i[4]-sale[j,4],i[5]-sale[j,5]

ift<qthenq:=t; f[i[1i[2i[3i[4i[5 procedureprint;

assign(output,name2);wrin(f[ed[1],ed[2],ed[3],ed[4],ed[5]]);

200例如：數(shù)字串1333規(guī)劃方程:F[I,J]=MIN{F[I-1,K]+NUM[K+1,J]}(I-1<=K<=J-1)邊界值:F[0,I]:= F[I，J]JINUM[I，J]IJ程序需要的空間約為20*200*200樣，復雜度就降到了2*200*200左右了。程序的時間效率約為20*200*200{$MprogramNoi96_4; f1,f2 :array[1..200]of^stype;{滾動數(shù)組} fi, n,m procedureinit;i,j,k:integer;n:=length(st);fori:=1to200beginnew(f1[i]);fillchar(f1[i]^,sizeof(f1[i]^),'0');end;fori:=1to200dobeginnew(f2[i]);fillchar(f1[i]^,sizeof(f1[i]^),'0');end;fori:=1tondof1[i]^:=functionbig(st1,st2:string):boolean;{判斷兩個字符串的大小}big:=(length(st1)>length(st2))(length(st1)=length(st2))and(st1>st2proceduresum(st1,st2:string;varst3:string);{高精度加法}i,j,k,l,o,p:integer;st3:=whilelength(st1)<length(st2)doinsert('0',st1,1);whilelength(st2)<length(st1)doinsert('0',st2,1);p:=0;foro:=length(st1)downto1dok:=(i+j+p)mod10;p:=(i+j+p)divst3:=chr(k+48)+st3;ifp>0thenst3:=chr(p+48)+while(st3[1]='0')and(length(st3)>1)dodelete(st3,1,1);proceduredynamic;{動態(tài)規(guī)劃}i,j,k,l,o,p:integer;st1,st2,st3 :string;fori:=1tomdoforj:=1to200forj:=i+1ton-m+idofork:=itoj-1if(k>=i)and(k<j)and(j-k<=101)thenifbig(f2[j]^,st3)or(f2[j]^='0')thenf2[j]^:=st3;forj:=1to200dof1[j]^:=f2[j]^;一個基元可以使用多次，也可不用。例如，序列ABABACABAAB可以由基元集合{A，AB，BA，CA，BBC}構(gòu)成。KK。請寫一個程序，對于輸入的基輸入數(shù)據(jù)：有兩個輸入文件（1<=L<=20'.',表示字符串結(jié)束。T的長度最小為1，最大不超過500000。5A 本題可以簡述為從一個集合里選出若干個基元,使其組成字符串T的前綴,求最長前Fii個字符的狀態(tài)，finda,ba至bFi=Fior(Fkandfindk1,i)(k=0..i-初始條件 Fi false(i由于T的長度最大達500000，無法存放所有狀態(tài)，但集合元長度不超過20，因態(tài)為true的字符的位置，即為所求?！怼硇稳纾簊[i,j]，表長度為i的第j亦可采用樹的結(jié)構(gòu)基元，構(gòu)造一種多叉樹（最多26叉，查找時順著相應字母，按樹結(jié)構(gòu)算，時間復雜度為充分利用基元長度不超過20這一條件。{$Mprogramioi96_5;constfn='input.txt';dn='data.txt';typetree=^node;node= :array['A'..'Z']of

procedurevar procedureget_tree(p:byte;varx:tree);vari ifp=len+1thenbegin ifx^.l[str[p]]=nilthenbeginfori:='A'to'Z'do

forch:='A'to'Z'doroot^.l[ch]:=nil;fori:=1tondobeginiflen>lthenl:=len;functionfind(str:string):boolean;vari fori:=1tolength(str)dobeginifx^.l[str[i]]=nilthenexit;

ifx^.athenprocedureout;

procedurevarst1,st2,st3 st2:='#';st3:='1';whilech<>'.'do fori:=length(st2)downtolength(st2)-l+1dobeginif(find(st1))and(st3[i-1]='1')thenbegin

iflength(st2)>length(st3)thenst3:=st3+'0';iflength(st2)>lthenbeginifn-tot>=lthenout;close(f);十八。多邊形（IOI98）（是否可改進，是時間復雜度降為N1N=4。每個頂點有一個整數(shù)標記，每條邊上有一個“+”號或“*”號。邊從1編號到N2-7+1 *5*4Figure1.一個多邊形的圖示 選擇一條邊EEV1和 V1V2E上的運算符運算的結(jié)果。132424+5*2-7+5*21

Figure2.拿走第3++*4242Figure3.拿走邊+4+4Figure4.拿走邊0200Figure5.拿走邊POLYGON.INNN。第32N1之間為頂點N）所示數(shù)據(jù)之間有一個空格。一條邊的標記為字母“t”(代表+)或者字母“x”(代表*)。樣例輸入4t-7t4x2x1所示的多邊形的輸入文件。之間有一個空格隔開。dbyoneSample11所示的例子中的結(jié)果。3N邊。比如我們刪除圖一多邊形中的1邊（圖二，圖三。2+- 1 * *4

+- 1 * *4

+- * *4---圖 圖n-1次刪邊操作后，“線”變成了一個點。我們的目的，就是安排以達到50，枚舉的復雜將會有50一定大于等于0；原題中邊可以為乘號，現(xiàn)在我們規(guī)定只能為加號。f(i,j) (f(k,i)f(jk,ikf(1,i)壞。我們可以一方程的基礎上進行改進（opr(i)表示第i條邊上的操作符）

opr(x2-1)=+時opr(x2-1)=-時f(i,j) act(k,i,jk,ikf(1,i)*3+2*-*3+2*-（-圖 什么fmax(i,j) actmax(k,i,jk,ik)kfmin(i,j) actmin(k,i,jk,ik)kf(1,i)actmaxactmin的構(gòu)造是十分關鍵的。首先討論actmax(x1,y1,x2,y2)的構(gòu)造：當opr(x2-1)=+時，，actmax=fmax(x1,y1)+fmax(x2,y2)當opr(x2-1)=*時，接下來討論actmin(x1,y1,x2,y2)的構(gòu)造：opr(x2-1)=+當opr(x2-1)=*時，要枚舉每一條邊，然后再用復雜度為十九?；ǖ隀淮安贾眉僭O你想以最美觀的方式布置花店的櫥窗。你有F束花，每束花的品種都不一樣，1V，V1V1至F定了花束在花瓶中排列的順序，即如果I＜j，則花束I必須放在花束j左邊的花瓶中。123，所有 123457--5--5--24假設條件1≤F≤100F1F。F≤V≤100，其中V是花瓶的數(shù)量。-50≤Aij≤50Aij是花束ij file），文件名是flower.inp。FVAij（i+1）j輸出flower.outFKK — — — — — — 2，考慮通過有向圖G來建立數(shù)學模型。假設有F束花，V個花瓶第i束花插入第j號花瓶看成一個點(i,j)，點(i,jij，為了體現(xiàn)出花束擺放的順序，從(i,j)向點(i+1,k)做有向弧，其中k>j增加源點S=(0,0T=(F+1,V+1S1,kF,k)向點T其中1≤k≤V。S和T的權(quán)均為0。f為圖GSTg由圖GS到T且長度為k的有向路徑P=(i0,j0)→(i1,j1)→…(ik,jk)，所以ix=x，k=F+1。我們把第x(1≤x≤F)束花放在第jx號花瓶中，由于jx>jx-1，該方案顯然符合題目的條件。對于任意的一個滿足題設的擺放方案，我們都可以類似的從圖G中找到STPP(x=1..F)A(x,jx)，注意到圖G中沒有環(huán)，這一點可以用反證法證明：若圖G中有一條有向圈P=(i0,j0)→(i1,j1)→…→(ik,jk)，其中(i0,j0)=(ik,jk)，而i0<i1<…ik，這與假設i0=ik設P[i,j]表示從原點S到頂點(i,j)的最長路徑的長度。由圖G的構(gòu)造可知，只有(i-1,0),(i-1,1),…,(i-1,j-1)到(i,j)有有向弧，且弧長都是A(i,j)。也就是說，從S到(i,j)的最長路徑長度，必然是由S到(i,k)的最長路徑長度加上A(i,j)所得，其中0≤k≤j-1。因此，我們有動態(tài)規(guī)劃P[i,0]=- 最大美學值即為P[F+1,V+1]。O(FV2)，仍然存在優(yōu)化的余地。設Q[i,j]=Max(0≤k≤j){P[i,k]}，代入①式，得 而Q[i,j]=Max{Q[i,j-1],P[i,j]} Q[i,0]:=-Q[i,j]:=Max{Q[i,j-1],Q[i-1,j-Q[F,V]改進后的算法時間復雜度和空間復雜度都是O(FV)。由于1≤F,V≤100，這樣的復雜GQiji二十。選課求選M門功課所得的最大學分。NMiSi，KiIKi=0SiIM若每一門功課定義一個時限，也就是說，其中，一些功課需學個學期，另外00之間連一條邊使森林成為一棵樹，如圖2。0347620347621475632002表jf(i,j)

02314756ba的右節(jié)點；如果節(jié)點b是節(jié)點ab02314756jf(I,j)i個節(jié)點為父節(jié)點，取j個子節(jié)點的最佳代價，這和前一個函數(shù)表示的jf(i,j)max(f(leftc,lcn)f(rightc,jn3，算十分優(yōu)秀圖 {$Q-,R-,S-{$Mconstmaxn=infile='input.txt';outfile='output.txt';typeflink=^ftype;fnode=recordln,value:integer;ftype=array[0..maxn]offnode;listtype=array[0..maxn]ofinteger;treenode=recordl,r,cost:integer;f:flink;treetype=array[-1..maxn]oftree:treetype;m,n:integer;procedureinit;lastc:listtype;fa,ch:assign(input,infile);reset(input);fillchar(lastc,sizeof(lastc),0);readln(m,n);tree[0].l:=-1;tree[0].r:=-1;forch:=0tomdowithtree[ch]dobeginl:=-1;r:=-forch:=1tomdobeginreadln(fa,tree[ch].cost);iflastc[fa]=0thenbeginlastc[fa]:=ch;tree[fa].l:=endelsebegintree[lastc[fa]].r:=ch;lastc[fa]:=ch;getmem(tree[-1].f,tree[-1].f^[1].value:=tree[-1].f^[0].value:=0;functiongetf(node:integer):integer;ln,rn,i,j,st,tar,max,maxj,p:integer;getf:=ifnode=-1thenexit;ln:=rn:=getf(tree[node].r);getmem(tree[node].f,(ln+rn+1)*4);fillchar(tree[node].f^,(ln+rn+1)*4,0);fori:=1toln+rndobeginmax:=0;maxj:=st:=i-rn;ifst<0thenst:=0;tar:=ln;ifi<tarthentar:=i;forj:=sttotardobeginp:=tree[tree[node].l].f^[j].value+tree[tree[node].r].f^[i-j].value;ifj>0thenbeginp:=tree[tree[node].l].f^[j-1].valuep:=p+tree[node].cost;ifp>maxthenbeginmax:=p;maxj:=tree[node].f^[i].value:=max;tree[node].f^[i].ln:=maxj;getf:=ln+rn;procedureprocedureprinttree(node,noden:integer);ifnoden<=0thenif(tree[node].f^[noden].ln>0)and(node<>0)thenwrin(node);printtree(tree[node].l,tree[node].f^[noden].ln-1);printtree(tree[node].r,noden-tree[node].f^[noden].ln);assign(output,outfile);rewrite(output);ifn<>1thenprinttree(0,n);

二十一。拯救大兵迷宮的外形是一個長方形，其在南北方向被劃分為N行，在東西方向被劃分為M列，于是整個迷宮被劃分為N*M個單元。我們用一個有序數(shù)對（單元的行號，單元的列號）來又或者存在一堵不可逾越的墻迷宮中有一些單元存放著并且所有的門被分為P類，相鄰單元的時間為1，拿取所在單元的的時間以及用開門的時間忽略不計。 （1<=I<=KGi>=1時，表示(Xi1,Yi1)單元與(Xi2,Yi2)Gi第K+3行是一個整數(shù)S，表示迷宮中存放的總數(shù)第K+3+J行(1<=J<=S)，有3個整數(shù)，依次為Xi1,Yi1,Qi：表示第J把存放(Xi1,Yi1)單元里，并且第J把是用來開啟第Qi類門的（其中1<=Qi<=P）輸出文件只包含一個整數(shù)T，表示麥克營救到大兵的最短時間的值，若不存在可4491223434422142N行M（1，1）到（nm）位的二進制數(shù)s來表示，若s的第I位為0，表示還沒有這種；相應的，若其第I位為1，則表示已經(jīng)有了。這樣最多有2^p種狀態(tài)。當我們手中的數(shù)增多時，s的值也在不斷地增加，這表示我們可以按s從小到大ss（I,j， if(stateand1shl(k-1)=0)and(f[State]^[I,j]+d[x,y]<f[state+1shl(k-1)])thenf[state+1shl(k-1)]:=f[State]^[I,j]+d[x,y];這種算法的空間復雜度為：2^maxp*maxn*maxm,約為230K，而時間復雜度為{$Mprogramlcy; = = = = = :array[1..4,1..2]ofshortint=((-1,0),(0,1),(0,- :array[0..10]ofinteger= =array[1..maxn,1..maxm]of =x,y,（位置kind（存放的種類）:byte; : : array1..maxn,1..maxm,1..4ofshortint（對于每個單元格， :array[0..maxn*maxm]of :array[0..1023]of :array[0..maxp]of : :array[1..maxn,1..maxm]ofprocedureinit; :x1,y1,x2,y2,gi,t:assign(fi,name1);reset(fi);assign(fo,name2);rewrite(fo);fori:=1tokdoif(x1>x2)or(x1=x2)and(y1>y2)thent:=x1;x1:=x2;t:=y1;y1:=y2;y2:=t;ifx1=x2ifgi=0thenbeging[x1,y1,2]:=-1;g[x2,y2,3]:=-1;endelsebeging[x1,y1,2]:=gi;g[x2,y2,3]:=gi;endelseifgi=0thenbeging[x1,y1,4]:=-1;g[x2,y2,1]:=-1;endelsebeging[x1,y1,4]:=gi;g[x2,y2,1]:=gi;end;fori:=1tokeynwithkey[i]dokey[0].x:=1;key[0].y:=1;key[0].kind:=0;procedureshortdis(stx,sty:byte;base:word); :array[1..maxn*maxm,1..2]ofbyte; :op:=1;que[1,1]:=stx;que[1,2]:=sty;whilecl<opdox:=que[cl,1];y:=que[cl,2];fori:=1to4doif(xxin[1..n])and(yyinand(g[x,y,i]>=0)and(hold[g[x,y,i]])and(d+1<dis[xx,yy])thenque[op,1]:=xx;que[op,2]:=yy;

procedurework; :word; :byte;fori:=0totwo[p+1]-1doiff[i]<>nilthenhold[0]:=true;（0forj:=1top hold[j]:=(iandtwo[j]>0);（將I轉(zhuǎn)換成其對應的每種是否經(jīng)擁有forj:=0tokeyndowithkey[j]doif(f[i]^[x,y]<ans){若此時所花費的時間就已經(jīng)超過當前最優(yōu)解，那么這個狀（n,mx+m-y個單位時間）thenifdis[n,m]<ansthenans:=dis[n,m];forq:=1tokeyndowithkey[q]ifnothold[kind]and(dis[x,y]<f[i+two[kind]]^[x,y])theniff[news]=nilthennew(f[news]);fillchar(f[news]^,sizeof(f[news]^),$ff);

procedureout;ifans=$ffffthenwrin(fo,'-1')elsewrin(fo,ans);

二十二。補丁VS錯誤就是人們所說的Bug。用戶在使用軟件時總是希望其錯誤越少越好，最好是沒有?。ㄓ袝r這種補丁甚至是的。T公司就是其中之一。上個月，T公司推出了一個新的字處理軟件，隨后了一批補丁。最近T公司發(fā)現(xiàn)nnT設此字處理軟件中可能出現(xiàn)的n個錯誤為集合B={b1,b2,…,bn}中的元素，T公司目前誤集合：Bi+,Bi-，當軟件包含了Bi+中的所有錯誤，而沒有包含Bi-中的任何錯誤時，補丁Pi才可以被使用，否則不能使用，顯然Bi+,Bi-的交集為空。補丁Pi將修復某些錯誤而同時加入某些錯誤，設錯誤集合Fi+,Fi-，使用過補丁Pi之后，F(xiàn)i-中的任何錯誤都不會在軟件中出現(xiàn)，而軟件將包含F(xiàn)i+中的所有錯誤，同樣Fi-,Fi+交集為空。另外，使用每個補丁TBn丁轉(zhuǎn)換成錯誤集合BA→B，其權(quán)值為補丁時間。這樣就將原題轉(zhuǎn)換成求有向圖的最短路徑問題。所以可以用Dijkstra的最短路徑算法，其狀態(tài)轉(zhuǎn)移方程為：n但是由于此題的頂點數(shù)可達到 n由于實際上并不會用到 下來，對這些點進行上述算法。方法是：從[1..nP（按n

)，由于{$Mprogramconstfinp =setof1..maxn; bug:set1; :array