【文章內(nèi)容簡介】 東界限逐步擴(kuò)展，也即矩形的寬度增加時，最大面積矩形區(qū)域的長度是（非嚴(yán)格）遞減的。 我們令 Max_wide[wno,eno]表示東西界限為 eno 和 wno 時的最大區(qū)域長度， 那么 Max_wide[wno,eno] ≤ Max_wide[wno,eno1]。所以我們可以得到下列兩個 38 38 33 39 39 40 39 39 39 40 41 38 36 39 39 39 1 確定西界限； 2 確定東界限（ ＜ 西界限 +100）； 3 對從西界限至東界限的每個單位區(qū)域進(jìn)行統(tǒng)計； 4 確定北界限 5 找到 最小的南界限； 38 38 33 39 39 40 39 39 39 40 41 38 36 39 39 39 38 38 33 39 39 40 39 39 39 40 41 38 36 39 39 39 38 38 33 39 39 40 39 39 39 40 41 38 36 39 39 39 規(guī)模化問題的解題策略 長沙市一中 ● 謝婧 9 剪枝條件： If 最大寬度（ Min{100,u}） * Max_wide[wno,eno1]當(dāng)前最大面積 Then 擴(kuò)展西界限； If (eno wno+1)* Max_wide[wno,eno1]當(dāng)前最大面積 Then 擴(kuò)展東界限； 下面我們就將方法一（ ）、方法二（ ）及結(jié)合剪枝條件后的方法二（ ）進(jìn)行測試時間的對照： 輸入數(shù)據(jù) 數(shù)據(jù)規(guī)模 (U,V,C) 運 行 時 間 1 20， 20， 0 2 30， 41， 5 3 100， 100， 2 4 100， 500， 7 5 300， 300， 10 6 500， 400， 10 7 600， 500， 5 8 700， 700， 9 9 700， 700， 10 （運行環(huán)境： pentium 166MHz/16MB） 注：數(shù)據(jù)是按規(guī)模從大到小進(jìn)行排列的。 測試結(jié)果分析： ⑴除數(shù)據(jù) 7 的運行時間與數(shù)據(jù)規(guī)模不相稱外，程序一的運行時間與數(shù)據(jù)規(guī)模相對穩(wěn)定，那主要是由于數(shù)據(jù) 7中相鄰正方形的高度差大多大于閾值 C。所以O(shè)(uv2C)是本算法的平均時間復(fù)雜度，它能夠較為準(zhǔn)確地反映其時間耗費。 ⑵對于規(guī)模遞增的數(shù)據(jù)，程序二的運行時間波動很大，尤其是數(shù)據(jù) 8 與數(shù)據(jù) 9，兩數(shù)據(jù)規(guī)模相差無幾，而運行結(jié)果卻大相徑庭。這 說明了 O(100uv2)僅僅是算法最壞情況下的時間復(fù)雜度。由于程序二的實際時間耗費對于數(shù)據(jù)規(guī)模的依賴性大，因此難以用時間復(fù)雜度較準(zhǔn)確地反映。 規(guī)?；瘑栴}的解題策略 長沙市一中 ● 謝婧 10 剪枝效果分析： 一旦確定剪枝條件，每次統(tǒng)計都會 執(zhí)行一次判斷操作，所以不精準(zhǔn)的剪枝會帶來很大的負(fù)面影響，再則 剪枝條件的效果常常被認(rèn)為存在很大的偶然性 。所以 它常常被人們冷落。 在上表中，相對于程序二，程序三的運行速度大大提高，且普遍優(yōu)于程序一，對比說明剪枝條件還是起到了很好的篩減作用。從其運行時間中，我們還能夠大致看出數(shù)據(jù)規(guī)模，盡管我們并不能精準(zhǔn)地估計出剪枝條件的效用到底 有多大，但這一相對穩(wěn)定性足以說明，使用優(yōu)秀的剪枝條件或者綜合使用多方面的剪枝條件，收益良好也就是“偶然”中的必然了。盡管剪枝不能降低算法的時間復(fù)雜度，但卻對降低實際時間耗費有著非同小可的作用。尤其是規(guī)?；瘑栴}，時間耗費大，如果注意分析問題，找到約束信息，必將起到事半功倍的效果。 （四）小 結(jié) 由于縱向擴(kuò)展問題具有很大的靈活性，很難像多維化問題那樣總結(jié)出一個統(tǒng)一的謀劃策略的思想，也難以歸納出較為完整的策略集，以上僅僅是我根據(jù)平時練習(xí)的經(jīng)驗總結(jié)出的自認(rèn)為有一定推廣意義的一些策略，其中也提到了剪枝在縱向擴(kuò)展問題 中的應(yīng)用，盡管它不是一個具體的策略，但對于規(guī)模化問題也有普遍意義，這已經(jīng)在上文中有所提及?？偠灾?，我們研究各種策略的目的是一致的，那就是要有效地解決問題。相信通過不斷的學(xué)習(xí)，并與其他同學(xué)以及教練們進(jìn)行交流探討，一定會探索出更多，更具價值的策略。 四 結(jié) 語 我們知道，無論算法如何優(yōu)化，所解決的問題規(guī)模終究是有限的，因此解決規(guī)模化問題時，首先應(yīng)明確問題的實際規(guī)模，然后 量“體”裁“衣”，設(shè)計適用的算法。有時題中還會對問題規(guī)模 加上了一定的限制條件，例如 IOI’99《隱藏的碼字》中，文本的最大長度為 1,000,000，而“右側(cè)最小”覆蓋序列的總數(shù)卻不超過 10,000 個，這就使得問題的實際規(guī)模大大降低。所以，審好題是解決規(guī)?；瘑栴}的第一步。 我們在信息學(xué)競賽中所解決的問題都是經(jīng)過實際問題理想化后的產(chǎn)物，而在現(xiàn)實生活中，真正需要處理和解決的是很大規(guī)模的數(shù)據(jù)量，這就是我們現(xiàn)在涉足規(guī)?；瘑栴}的一大現(xiàn)實意義，同時規(guī)?；瘑栴}也向我們提出了更高層次的要求。值得注意的是，規(guī)?；瘑栴}固然重要，但它并不是空中樓閣，它是建立在小規(guī)模問題基礎(chǔ)上的，因此，想要很好地解決規(guī)?；瘑栴}，必須從基礎(chǔ)做起，這樣的道理也不只是適應(yīng)于信息 學(xué)競賽的。既具備扎實的理論基礎(chǔ)，又具有實干本領(lǐng)和創(chuàng)新精神，是時代對于跨世紀(jì)青年的基本要求，也是我們不息奮斗的目標(biāo)。 規(guī)?；瘑栴}的解題策略 長沙市一中 ● 謝婧 11 【附錄】 [1] 本文提到的“降維”是一種謀劃策略的思想，與通常意義上的降維一定區(qū)別。 【程序】 1 由于枚舉法效率太低，因此僅給出有效算法的程序。 program object。 type node=record{存儲高精度整數(shù) } v:array[1..100] of longint。 last:integer。 end。 var n,i:integer。 a:array[1..10] of integer。{存儲 n維體的信息 } tot:node。{階積和 } procedure readn。{讀入 n維體的信息 } var i:integer。 f:text。 begin assign(F,39。39。)。reset(F)。 readln(F,n)。 for i:=1 to n do read(f,a[i])。 close(f)。 end。 function num(s:integer):longint。 begin num:=(s+2)*(s+1)*s div 6。 end。 procedure multiply(var nd:node。s:longint)。{高精度乘法 } var c:longint。 i:integer。 begin c:=0。 with nd do begin for i:=1 to last do 規(guī)?；瘑栴}的解題策略 長沙市一中 ● 謝婧 12 begin v[i]:=v[i]*s+c。 c:=v[i] div 10。 v[i]:=v[i] mod 10。 end。 while c0 do begin inc(last)。 v[last]:=c mod 10。 c:=c div 10。 end。 end。 end。 begin readn。 with tot do begin fillchar(v,sizeof(v),0)。 v[1]:=1。last:=1。 end。{初始化 } for i:=1 to n do multiply(tot,num(a[i]))。{計算階積和 } with tot do{輸出結(jié)果 } for i:=last downto 1 do write(v[i])。 writeln。 end. 2 由于方法一效率太低，方法二無法實現(xiàn)，僅給出對應(yīng)方法三的程序。 program number。 const inputfile=39。39。 outputfile=39。39。 var f:text。 n,m:longint。 mb:longint。{儲存當(dāng)前真因子個數(shù)最多的數(shù) } fn:integer。{儲存當(dāng)前真因子個數(shù)最多的數(shù)所包含的真因子個數(shù) } s,t,i,j:longint。{ s+1,t 為分段統(tǒng)計時的起點、終點 } a:array[1..30000] of integer。 {每次統(tǒng)計連續(xù) 30000 個數(shù)的真因子個數(shù) ,包括每個數(shù)本身 } 規(guī)?；瘑栴}的解題策略 長沙市一中 ● 謝婧 13 procedure readn。 begin assign(f,inputfile)。 reset(F)。 readln(f,n,m)。 close(F)。 end。 function max(x,y:longint):longint。{返回 x,y 中大的值 } begin if xy then max:=x else max:=y。 end。 procedure output。 begin assign(F,outputfile)。 rewrite(F)。 writeln