【文章內(nèi)容簡(jiǎn)介】 to 1 do if not ((i=21) and (j=0)) and not ((i=1) and (j=1)) then pf[i,j]:=pare0(font[(t1)*20+ij],dd[k+i1])。 {用破損字形第i行與標(biāo)準(zhǔn)字形第i行、第i1行比較，記錄差別} l1[1]:=pf[1,0]。 {l1[i]為前i行與標(biāo)準(zhǔn)前i行匹配的差別} for i:=2 to 20 do l1[i]:=l1[i1]+pf[i,0]。 l2[22]:=0。 {l2[i]為第i行開始的內(nèi)容與標(biāo)準(zhǔn)從i1行開始的內(nèi)容進(jìn)行匹配的差別} for i:=21 downto 2 do l2[i]:=l2[i+1]+pf[i,1]。 bb:=maxint。 for i:=1 to 20 do {比較20種方式} if l1[i1]+l2[i+1]+pf[i,0]bb then bb:=l1[i1]+l2[i+1]+pf[i,0]。 if bbbest then begin best:=bb。 ff:=t end。 end。 pare21:=bestend。begin {主程序} assign(f,39。39。)。 reset(f)。 assign(f1,39。39。)。 reset(f1)。 assign(f2,39。39。)。 rewrite(f2)。 {文件關(guān)聯(lián)} readln(f,k)。 {讀入行數(shù)540} bin[1]:=1。 for i:=2 to 20 do bin[i]:=bin[i1]*2。 {生成bin數(shù)組，為2的冪} for i:=1 to k do begin readln(f,str)。 getnum(font[i])。 {stringlongint轉(zhuǎn)換} end。 read(f1,n)。 {讀入分析文件的各行} for i:=1 to n do begin readln(f1,str)。 getnum(dd[i])。 {stringlongint轉(zhuǎn)換} end。 fillchar(pro,sizeof(pro),255)。 {初值65535} fillchar(sta,sizeof(sta),0)。 {每步分析出的最優(yōu)字符} fillchar(bf,sizeof(bf),255)。 {每步分析出的最優(yōu)切割} pro[0]:=0。 sta[0]:=0。 bf[0]:=0。 for i:=19 to n do {考慮19行至n行} begin if (i=19) and (pro[i19]65535) then {如果切去一個(gè)19行字符后的情況可能} begin t:=pare19(i19+1,ff)。 {比較從i19+1起19行與標(biāo)準(zhǔn)結(jié)果最接近的結(jié)果與差別} if t+pro[i19]pro[i] then {如果更優(yōu)，更新動(dòng)態(tài)規(guī)劃數(shù)組} begin pro[i]:=t+pro[i19]。 sta[i]:=ff。 bf[i]:=i19。 end。 end。 if (i=20) and (pro[i20]65535) then {如果切去一個(gè)20行字符后的情況可能} begin t:=pare20(i20+1,ff)。 {比較從i20+1起20行與標(biāo)準(zhǔn)結(jié)果最接近的結(jié)果與差別} if t+pro[i20]pro[i] then {如果更優(yōu)，更新動(dòng)態(tài)規(guī)劃數(shù)組} begin pro[i]:=t+pro[i20]。 sta[i]:=ff。 bf[i]:=i20。 end。 end。 if (i=21) and (pro[i21]65535) then {如果切去一個(gè)21行字符后的情況可能} begin t:=pare21(i21+1,ff)。 {比較從i21+1起21行與標(biāo)準(zhǔn)結(jié)果最接近的結(jié)果與差別} if t+pro[i21]pro[i] then {如果更優(yōu)，更新動(dòng)態(tài)規(guī)劃數(shù)組} begin pro[i]:=t+pro[i21]。 sta[i]:=ff。 bf[i]:=i21。 end。 end。 end。 str:=39。39。 i:=n。 if pro[n]=65535 then begin writeln(f2,39。No answer.39。)。 close(f1)。 close(f2)。 halt end。 {如果無(wú)解} while i0 do {倒推求解} begin str:=cc[sta[i]]+str。 i:=bf[i]。 end。 writeln(f2,str)。 {輸出} close(f1)。 close(f2)end.程序2 NOI’97積木游戲{說(shuō)明：}{為防止出現(xiàn)內(nèi)存溢出，程序采用逐級(jí)遞推的方式。}program Toy_Bricks_Game。 {積木游戲}type jmtype=array [0..100] of ^node。 {動(dòng)態(tài)規(guī)劃過(guò)程中僅保留與當(dāng)前最接近的一個(gè)階段的情況} {這是存儲(chǔ)一個(gè)階段的量的指針類型} node=array [0..300] of longint。var f1,f2:text。 {文件變量} size:array [0..300,1..2] of word。 {各個(gè)出現(xiàn)的面的記錄,0對(duì)應(yīng)無(wú)面積要求} num:integer。 {記錄的不同面數(shù)} n,m:integer。 {積木數(shù)、堆成的堆數(shù)} i,j,k,t:integer。 {輔助變量} p,q,r:jmtype。 {遞推階段指針數(shù)組，每個(gè)保留一個(gè)階段（K值），從p到q，r用于交換} aa:array [1..100,1..3] of word。 {邊長(zhǎng)數(shù)據(jù)} ss:array [1..100,1..3] of word。 {3個(gè)面對(duì)應(yīng)的面序號(hào)，對(duì)同樣長(zhǎng)、寬的面作了優(yōu)化}procedure sort(i:integer)。 {對(duì)第i個(gè)長(zhǎng)方體的三邊長(zhǎng)排序}var j,k,t:integer。begin for j:=1 to 2 do for k:=j+1 to 3 do if aa[i,j]aa[i,k] then begin t:=aa[i,j]。 aa[i,j]:=aa[i,k]。 aa[i,k]:=t end。end。function add(a1,a2:integer):integer。 {在面標(biāo)記中增添當(dāng)前面，并返回相應(yīng)的序號(hào)}var i,j:integer。begin for i:=1 to num do if (a1=size[i,1]) and (a2=size[i,2]) then begin add:=i。 exit end。 inc(num)。 size[num,1]:=a1。 size[num,2]:=a2。 add:=num。end。procedure preprocess。 {預(yù)處理，將要處理的面記入}var i,j,k:integer。begin num:=0。 for i:=1 to n do begin sort(i)。 ss[i,1]:=add(aa[i,1],aa[i,2])。 ss[i,2]:=add(aa[i,1],aa[i,3])。 ss[i,3]:=add(aa[i,2],aa[i,3])。 end。end。procedure check(ii,nn,hh:integer)。 {檢查用ii積木的nn放置方式，是否有效}var g,h:integer。begin if (p[ii1]^[0]=0) and (p[ii1]^[0]+hh=q[ii]^[j]) then q[ii]^[j]:=p[ii1]^[0]+hh。 {考慮另成一堆} if (p[ii1]^[ss[ii,nn]]=0) and (q[ii1]^[ss[ii,nn]]+hh=q[ii]^[j]) then q[ii]^[j]:=q[ii1]^[ss[ii,nn]]+hh。 {考慮放在前一堆上}end。begin assign(f1,39。39。)。 reset(f1)。 assign(f2,39。39。)。 rewrite(f2)。 {文件關(guān)聯(lián)、打開} readln(f1,n,m)。 {讀入N、M值} for i:=1 to n do {讀入邊長(zhǎng)} readln(f1,aa[i,1],aa[i,2],aa[i,3])。 size[0,1]:=0。 size[0,2]:=0。 preprocess。 {生成各種待處理的面} for i:=0 to n do {動(dòng)態(tài)內(nèi)存初始化} begin new(p[i])。 new(q[i])。 fillchar(q[i]^,sizeof(q[i]^),0)。 end。 for t:=1 to m do {連續(xù)遞推M階段,分成T堆} begin r:=q。 q:=p。 p:=r。 {交換P、Q} for i:=0 to n do fillchar(q[i]^,sizeof(q[i]^),255)。 {Q初始化} for i:=t to n do {考慮T個(gè)到N個(gè)積木} begin for j:=0 to num do {考慮最后“輸出”的面的約束條件} begin q[i]^[j]:=q[i1]^[j]。 {當(dāng)前積木不用} if (aa[i,1]=size[j,1]) and (aa[i,2]=size[j,2]) then check(i,1,aa[i,3])。 if (aa[i,1]=size[j,1]) and (aa[i,3]=size[j,2]) then check(i,2,aa[i,2])。 if (aa[i,2]=size[j,1]) and (aa[i,3]=size[j,2]) then check(i,3,aa[i,1])。 {如果當(dāng)前積木的某方向放置可以滿足此要求，考慮按此方向放置該塊作為新的一堆的底或加在前一堆上（如果可能）} end。 end。 end。 writeln(f2,q[n]^[0])。 {輸出答案} close(f1)。 close(f2)end.程序3 IOI’98 多邊形program Polygon。 {“多邊形”程序}var f1,f2:text。 {輸入、輸出文件變量} n:integer。 {頂點(diǎn)個(gè)數(shù)} data:array [1..50] of integer。 {原始數(shù)據(jù)頂點(diǎn)} sign:array [1..50] of char。 {原始數(shù)據(jù)運(yùn)算符} i,j,k,l:integer。 {輔助變量} t,s,p:integer。 {輔助變量} ans:set of 1..50。 {可能達(dá)到最大值的第一次移動(dòng)的邊的序號(hào)} best:integer。 {當(dāng)前最優(yōu)解} min,max:array [1..50,0..50] of integer。 {動(dòng)態(tài)規(guī)劃表格，min[i,l]表示從第i個(gè)頂點(diǎn)開始，經(jīng)過(guò)l個(gè)符號(hào)按合理運(yùn)算所得的結(jié)果的最小值；max與之類似，但為最大值} first:boolean。 {首次輸出標(biāo)志}procedure init。 {初始化，讀入原始數(shù)據(jù)}var i:integer。 ch:char。begin readln(f1,n)。 for i:=1 to n do begin repeat read(f1,ch)。 until ch39。 39。 sign[i]:=ch。 {sign[i]位于data[i]與其后頂點(diǎn)間} read(f1,data[i])。 end。end。begin {文件關(guān)聯(lián)、打開} assign(f1,39。39。)。 reset(f1)。 assign(f2,39。39。)。 rewrite(f2)。 {初始化} init。 {賦初值} best:=maxint1。 ans:=[]。 fillchar(max,sizeof(max),0)。 fillchar(min,sizeof(min),0)。 {數(shù)組初始化} for j:=1 to n do begin max[j,0]:=data[j]。