規(guī)?；瘑?wèn)題的解題策略-資料下載頁(yè)
2025-06-07 22:16本頁(yè)面
【正文】 。 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)。 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 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為西面界限且其東面界限不超過(guò)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} {若可能得到的最大面積仍不能超過(guò)當(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]。 if max[k]maxall then maxall:=max[k]。 {在從k到j(luò)的區(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)。 assign(f,outputfile)。rewrite(F)。 writeln(f,area)。 writeln(f,xmin,39。 39。,ymin,39。 39。,xmax,39。 39。,ymax)。 close(F)。end.【參考書(shū)目】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é)出版社 21
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1