算法合集之規(guī)?；瘑栴}的解題策略-資料下載頁(yè)
2025-01-09 09:23本頁(yè)面
【正文】 rue=false。 end。 end。 end。 begin area:=1。 xmin:=1。xmax:=1。 ymin:=1。ymax:=1。 {區(qū)域信息初始化 } assign(f,inputfile)。 SetTextBuf(F, Buf)。 reset(F)。 readln(F,u,v,c)。 if 100u then maxarea:=longint(v)*longint(u) else maxarea:=longint(v)*100。 for i:=1 to 100 do new(map[i])。 get(1,100)。 for i:=1 to u99 do begin done(i,i+99)。 dispose(map[i])。{釋放空間 } 規(guī)模化問題的解題策略 長(zhǎng)沙市一中 ● 謝婧 18 if area=maxarea then break。{已經(jīng)達(dá)到了最大面積的上限，跳出循環(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(i+100,i+last+99)。 end。 end。 for i:=(u div last*last)+1 to u do new(map[i])。 get((u div last*last)+1,u)。 {讀入剩余數(shù)據(jù) } for i:=u98 to u do if i0 then done(i,u)。 close(F)。 assign(f,outputfile)。rewrite(F)。 writeln(f,area)。 writeln(f,xmin,39。 39。,ymin,39。 39。,xmax,39。 39。,ymax)。 close(F)。 end. {$A+,B,D+,E+,F,G,I+,L+,N,O,P,Q,R,S+,T,V+,X+} {$M 2048,0,655360} program land_3。 const maxn=700。 last=100。{一次性讀入的區(qū)域列數(shù)（東西方向） } inputfile=39。39。 outputfile=39。39。 type arr=array[0..maxn] of integer。 maptype=array[1..maxn] of ^arr。 var f:text。 u,v,c,i,j:integer。 xmin,ymin,xmax,ymax:integer。{機(jī)場(chǎng)所在區(qū)域的信息 } map:maptype。{地圖 } min,max:array[1..maxn] of integer。{分別存儲(chǔ)一定區(qū)域內(nèi) 的最小高度、最大高度 } area,maxarea:longint。{（ area當(dāng)前的最大面積； maxarea最大面積的上限；） } Buf:array[1..8191] of Char。 { 8K buffer；緩沖區(qū) } procedure get(left,right:integer)。{讀入地圖的 left列至 right列 } var i,j,k,no:integer。 begin 規(guī)?；瘑栴}的解題策略 長(zhǎng)沙市一中 ● 謝婧 19 reset(F)。 for i:=v downto 1 do begin readln(F)。 for j:=1 to left1 do read(f,k)。 for no:=left to right do if no=u then read(f,map[no]^[i]) else break。 end。 end。 procedure done(stl,edl:integer)。 {求解以 stl為西面界限且其東面界限不超過 edl 中的最大區(qū)域 } var i,j,k,w,l:integer。 {w當(dāng)前區(qū)域沿東西向的正方形數(shù)目 } minall,maxall:integer。 begin if longint(edlstl+1)*longint(v)=area then exit。 for i:=1 to v do min[i]:=maxint。 for i:=1 to v do max[i]:=maxint。 w:=0。{沿東西方向的長(zhǎng)度 } l:=v。{沿南北方向的最大寬度 } for i:=stl to edl do begin{區(qū)域的東面界限 } for j:=1 to v do begin if map[i]^[j]min[j] then min[j]:=map[i]^[j]。 {j行中從 stl 列至 i列中的最小高度 } if map[i]^[j]max[j] then max[j]:=map[i]^[j]。 {j行中從 stl 列至 i列中的最大高度 } end。 inc(w)。 if longint(edlstl+1)*longint(l)=area then break。{剪枝條件 1} if longint(w)*longint(l)=area then continue。 {剪枝條件 2} {若可能得到的最大面積仍不能超過當(dāng)前的最大面積 } l:=0。{重新計(jì)算 L值 } for j:=1 to v do begin{區(qū)域的北面界限 } k:=j+1。{區(qū)域的南面界限 } minall:=maxint。maxall:=maxint。 repeat dec(k)。 if k=0 then break。 if min[k]minall then minall:=min[k]。 規(guī)模化問題的解題策略 長(zhǎng)沙市一中 ● 謝婧 20 if max[k]maxall then maxall:=max[k]。 {在從 k到 j 的區(qū)域中高度的最小、最大值分別為 minall,maxall} until maxallminallc。 {所得的區(qū)域是南北方向上的跨度為 [k+1,j]} if jkl then l:=jk。{更新 L值 } if longint(w)*longint(jk)area then begin area:=longint(w)*longint(jk)。 xmin:=stl。 xmax:=i。 ymin:=k+1。 ymax:=j。 end。 end。 end。 end。 begin area:=1。 xmin:=1。xmax:=1。 ymin:=1。ymax:=1。 {區(qū)域信息初始化 } assign(f,inputfile)。 SetTextBuf(F, Buf)。 reset(F)。 readln(F,u,v,c)。 if 100u then maxarea:=longint(v)*longint(u) else maxarea:=longint(v)*100。 for i:=1 to 100 do new(map[i])。 get(1,100)。 for i:=1 to u99 do begin done(i,i+99)。 dispose(map[i])。{釋放空間 } if area=maxarea then break。{已經(jīng)達(dá)到了最大面 積的上限，跳出循環(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(i+100,i+last+99)。 end。 end。 for i:=(u div last*last)+1 to u do new(map[i])。 get((u div last*last)+1,u)。 {讀入剩余數(shù)據(jù) } for i:=u98 to u do if i0 then done(i,u)。 close(F)。 規(guī)?；瘑栴}的解題策略 長(zhǎng)沙市一中 ● 謝婧 21 assign(f,outputfile)。rewrite(F)。 writeln(f,area)。 writeln(f,xmin,39。 39。,ymin,39。 39。,xmax,39。 39。,ymax)。 close(F)。 end. 【參考書目】 1．《實(shí)用算法分析與程序設(shè)計(jì)》 吳文虎 王建德 電子工業(yè)出版社 2．《青少年國(guó)際和全國(guó)信息學(xué)（計(jì)算機(jī)）奧林匹克競(jìng)賽指導(dǎo) —— 組合數(shù) 學(xué)的算法與程序設(shè)計(jì)》 吳文虎 王建德 清華大學(xué)出版社 3.《數(shù)據(jù)結(jié)構(gòu)》（第二版） 嚴(yán)蔚敏 吳偉民 清華大學(xué)出版社
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1