【正文】 ,ymax)。,ymin,39。rewrite(F)。 get((u div last*last)+1,u)。 get(i+100,i+last+99)。 for i:=1 to u99 do begin done(i,i+99)。 readln(F,u,v,c)。ymax:=1。begin area:=1。 end。 xmin:=stl。 if max[k]maxall then maxall:=max[k]。maxall:=maxint。{剪枝條件1} if longint(w)*longint(l)=area then continue。 {j行中從stl列至i列中的最小高度} if map[i]^[j]max[j] then max[j]:=map[i]^[j]。 for i:=1 to v do max[i]:=maxint。{求解以stl為西面界限且其東面界限不超過edl中的最大區(qū)域}var i,j,k,w,l:integer。 for no:=left to right do if no=u then read(f,map[no]^[i]) else break。{讀入地圖的left列至right列}var i,j,k,no:integer。{地圖} min,max:array[1..maxn] of integer。var f:text。 outputfile=39。const maxn=700。 39。 39。 assign(f,outputfile)。 for i:=(u div last*last)+1 to u do new(map[i])。{已經(jīng)達到了最大面積的上限，跳出循環(huán)} if (i mod last=1) and (i+last+99=u) then begin{讀入下一輪數(shù)據(jù)} for j:=i+100 to i+last+99 do new(map[j])。 get(1,100)。 reset(F)。 ymin:=1。end。 if len[j,k0]wide[k] then wide[k]:=len[j,k0]。 inc(j)。xmax:=xmin+wide[k]1。 j:=i。 end。max:=min+c。begin if longint(edlstl+1)*longint(v)=area then exit。procedure done(stl,edl:integer)。 for j:=1 to left1 do read(f,k)。procedure get(left,right:integer)。{地圖} area,maxarea:longint。var f:text。39。 last=100。end.4 問題四IOI’99《機場跑道》，由于效果不很明顯，因此沒有著重討論。 assign(F,outputfile)。 ans_wd:=wd。{大于前驅(qū)單詞的長度，跳出循環(huán)} wd[length(wd)]:=upcase(wd[length(wd)])。{前綴詞鏈個數(shù)清零}
for i:=1 to length(wd) do
if i=l then begin if prev[i]=upcase(wd[i]){含有一個前綴單詞} then begin inc(now)。{讀入一個單詞}
if wd=39。 prev:=39。 writeln(F)。{wd——當(dāng)前單詞；prev——前驅(qū)單詞；ans_wd——最長詞鏈} now,max,i,l:integer。39。const maxn=75。 end。 {統(tǒng)計完全平方數(shù)} for i:=1 to ts do{將本區(qū)間的統(tǒng)計結(jié)果與已知最優(yōu)值比較、取優(yōu)} if a[i]fn then begin fn:=a[i]。 fillchar(a,sizeof(a),0)。 fn:=0。 close(F)。procedure output。end。begin assign(f,inputfile)。{儲存當(dāng)前真因子個數(shù)最多的數(shù)} fn:integer。39。program number。{初始化} for i:=1 to n do multiply(tot,num(a[i]))。 with tot do begin fillchar(v,sizeof(v),0)。 end。 end。begin c:=0。procedure multiply(var nd:node。end。reset(F)。 f:text。 a:array[1..10] of integer。type node=record{存儲高精度整數(shù)} v:array[1..100] of longint。既具備扎實的理論基礎(chǔ)，又具有實干本領(lǐng)和創(chuàng)新精神，是時代對于跨世紀(jì)青年的基本要求，也是我們不息奮斗的目標(biāo)。有時題中還會對問題規(guī)模加上了一定的限制條件，例如IOI’99《隱藏的碼字》中，文本的最大長度為1,000,000，而“右側(cè)最小”覆蓋序列的總數(shù)卻不超過10,000個，這就使得問題的實際規(guī)模大大降低。（四）小 結(jié)由于縱向擴展問題具有很大的靈活性，很難像多維化問題那樣總結(jié)出一個統(tǒng)一的謀劃策略的思想，也難以歸納出較為完整的策略集，以上僅僅是我根據(jù)平時練習(xí)的經(jīng)驗總結(jié)出的自認(rèn)為有一定推廣意義的一些策略，其中也提到了剪枝在縱向擴展問題中的應(yīng)用，盡管它不是一個具體的策略，但對于規(guī)模化問題也有普遍意義，這已經(jīng)在上文中有所提及。在上表中，相對于程序二，程序三的運行速度大大提高，且普遍優(yōu)于程序一，對比說明剪枝條件還是起到了很好的篩減作用。這說明了O(100uv2)僅僅是算法最壞情況下的時間復(fù)雜度。所以我們可以得到下列兩個剪枝條件： If 最大寬度（Min{100,u}）* Max_wide[wno,eno1]當(dāng)前最大面積 Then 擴展西界限； If (eno wno+1)* Max_wide[wno,eno1]當(dāng)前最大面積 Then 擴展東界限；下面我們就將方法一（）、方法二（）及結(jié)合剪枝條件后的方法二（）進行測試時間的對照： 輸入數(shù)據(jù) 數(shù)據(jù)規(guī)模 (U,V,C)運 行 時 間120，20，0230，41，53100，100，24100，500，75300，300，106500，400，107600，500，58700，700，99700，700，10（運行環(huán)境：pentium 166MHz/16MB）注：數(shù)據(jù)是按規(guī)模從大到小進行排列的。38383339394039393940413836393939由于我們求找面積最大的矩形區(qū)域會不斷更新當(dāng)前的最優(yōu)值，所以，如果某次計算所能得到的最大面積不超過當(dāng)前的最優(yōu)值，則這樣的計算毫無意義，可以省略。方法二將矩陣進行橫向壓縮，得到一系列單位區(qū)域，然后求最長的連續(xù)單位區(qū)域。 所以下限為36的面積最大區(qū)域為（1,1,4,2）。 問題四：IOI’99《機場跑道》。剪枝就是通過某種判斷，篩減掉一些不必要的計算過程。精簡法的特點：精簡法在于抓住問題的本質(zhì)，升華元素的內(nèi)在聯(lián)系，淡化元素的孤立性，將大規(guī)模的數(shù)據(jù)抽象成簡單、明了的關(guān)系，使得問題更易于描述，實際操作更加簡化。動態(tài)規(guī)劃的方法盡管在求“數(shù)列的最長非降子序列”中得到了很好的效果，但卻不適應(yīng)本題，主要基于這幾個原因：⑴字串的存儲比數(shù)列元素復(fù)雜，使得空間耗費大；⑵字串的包含關(guān)系比數(shù)列元素的大小關(guān)系復(fù)雜，使得時間耗費大；⑶單詞表的元素存在有序性，使得我們能夠根據(jù)問題良好的特性設(shè)計最為適用的算法。如下表：i；int；integer；intern；internet；integerinterninternet首先，i和int被標(biāo)記為后繼單詞integer的前綴，待讀入單詞intern后，我們只需將單詞integer與intern比較，就得出了它的前綴詞鏈i和int，最后處理internet，得出上表中的最長詞鏈為i；int；intern；internet。簡證如下：令w2=L1L2L3..L