這篇解題報(bào)告是對(duì)我最近一些題的總結(jié)，里面的代碼都是我解題，優(yōu)化，再優(yōu)化的過(guò)程的記錄，記錄了自己對(duì)算法的完善與優(yōu)化思路，還有對(duì)編程哲學(xué)的理解：do it,do it well。

很感謝孫老師您，讓自己可以找到利用計(jì)算機(jī)作比只是單純玩游戲更有意義又更有趣的事情，又通過(guò)您的課，通過(guò)照著您給的路自己不斷探索，感覺(jué)自身能力得到了很大的提升，從當(dāng)時(shí)一個(gè)小程序漏洞百出，思路拙劣，對(duì)oj系統(tǒng)的不熟悉，甚至當(dāng)時(shí)上課時(shí)平時(shí)的練習(xí)和考試都讓自己感覺(jué)不盡人意，到現(xiàn)在自己不斷地追求完善代碼完善思路，追求完美追求最優(yōu)，雖然還是拙劣但是感覺(jué)自己在努力，感覺(jué)在自己現(xiàn)有的知識(shí)程度上已經(jīng)做的很美了，這種在心里涌上的孜孜不倦的追求的感覺(jué)讓自己感覺(jué)到了人生的意義，正如歌德在《浮士德》里所表達(dá)的主題一樣，完善的境界永遠(yuǎn)不可及，人類(lèi)所能達(dá)到的最高成就，恰在于一種自強(qiáng)不息的創(chuàng)造性生活本身，一種不斷進(jìn)步的道路與過(guò)程本身。

好了，說(shuō)了那么多，該切入正題了，審視自身的努力，反思自己的不足，就可以很清楚的一個(gè)菜鳥(niǎo)標(biāo)準(zhǔn)的特征是：耗時(shí)費(fèi)力的暴力枚舉浪費(fèi)了大量資源，永遠(yuǎn)不變的單一的選擇排序，不自覺(jué)暴露出的goto使用……所以我今天借三個(gè)同樣是關(guān)于求出最優(yōu)解的問(wèn)題，來(lái)說(shuō)明我是怎么沖出暴力枚舉。

第一個(gè)問(wèn)題，很簡(jiǎn)單，是ustcoj上的1389,連續(xù)子數(shù)組的和，題目大意如下：輸入一個(gè)整型數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。求所有子數(shù)組的和的最大值。(數(shù)組里的元素可正可負(fù))

想都不用想，直接暴力枚舉，太容易了，且只是個(gè)o(n^2)的算法，由于n小于5000，必然不用當(dāng)心超時(shí)，直接用暴力枚舉就可以過(guò)了，看代碼：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

#include <stdio.h> #define max 5000 int a[max+1]; int qiuzhi(int n)???????????????? //枚舉所有的情況，返回里面的最大值 { ????????int i,j,ans,temp; ????????ans=a[0]; ????????for(i=0;i<n;i++) ????????{ ?????????????????temp=a[i]; ?????????????????if(temp>ans) ???????????????????????????????????ans=temp; ?????????????????for(j=i+1;j<n;j++) ?????????????????{ ??????????????????????????temp+=a[j]; ??????????????????????????if(temp>ans) ???????????????????????????????????ans=temp; ?????????????????} ????????} ????????return ans; } int main() { ????????int n,i,answer; ????????while(scanf("%d",&n)) ????????{ ?????????????????if(n==0) ??????????????????????????break; ?????????????????for(i=0;i<n;i++) ??????????????????????????scanf("%d",&a[i]); ?????????????????answer=qiuzhi(n); ?????????????????printf("%d\n",answer); ????????} ????????return 0; }

解釋都不必了，就是把所有的子序列的和枚舉一遍求出它的最大值，看不懂的話(huà)就好好回頭學(xué)好基本功。你可以寫(xiě)出這些代碼就停了，畢竟accept萬(wàn)歲!深有體會(huì)，一個(gè)accept不容易啊,但你就這樣放著它不管了，你就永遠(yuǎn)只會(huì)到這個(gè)水平，永遠(yuǎn)得不到提升，看看有些問(wèn)題的排行榜，看看上面的大神們，有時(shí)幾乎從第一名到第十名都是同一個(gè)大神，足以看出他們不滿(mǎn)足于僅僅的accept，也足以理解他們?yōu)槭裁从心敲磸?qiáng)的能力。永遠(yuǎn)記住有完成，就可以更好的完成，有優(yōu)就有更優(yōu)。永遠(yuǎn)相信當(dāng)前的方案不是最好的，為求完善孜孜不倦！

回過(guò)頭來(lái)，仔細(xì)想想，對(duì)于這樣一個(gè)問(wèn)題，o(n^2)的時(shí)間復(fù)雜度是不是太大了，是不是可以繼續(xù)縮短它運(yùn)行時(shí)和所耗的空間。我們要達(dá)成這樣的目的，仔細(xì)來(lái)看要，無(wú)非可以從兩方面入手，一是先通過(guò)特殊處理來(lái)減少枚舉的復(fù)雜度；二是減少枚舉的次數(shù)。這些也是我對(duì)做過(guò)的這些題目?jī)?yōu)化過(guò)程的總結(jié)。要完成這兩個(gè)方面，一即通過(guò)一些搜索、排序等增加有序度的運(yùn)算來(lái)將難以辦到的枚舉變得簡(jiǎn)單；二即從問(wèn)題條件入手通過(guò)推理找到一些隱性的條件，增加這些隱性的條件來(lái)減少枚舉次數(shù)。我們來(lái)看這個(gè)問(wèn)題，它說(shuō)要找到所有子數(shù)組的和的最大值，這個(gè)最大值滿(mǎn)足些什么特征呢？或者說(shuō)這個(gè)和最大的子數(shù)組滿(mǎn)足些什么特征呢？至少我們可以找到這一條特征，這個(gè)子數(shù)組里的第一個(gè)數(shù)必然不可能小于零，為方便我們不妨稱(chēng)之為定理一。定理一很好理解，用反證法，如果這個(gè)子數(shù)組的第一個(gè)數(shù)小于零了，去掉它的第一個(gè)數(shù)所得的子數(shù)組必然比它要大，這與它的和最大相矛盾，所以定理一成立。我們根據(jù)這個(gè)條件可以在枚舉加入此條件，減少枚舉次數(shù)：

for(i=0;i<n;i++)

{

?? if(a[i]<0)

????? continue;

?? ……

}

雖然這樣算法的時(shí)間變的不穩(wěn)定，我不會(huì)求它的時(shí)間復(fù)雜度了，但可以肯定對(duì)于大多數(shù)時(shí)候比之前要快很多了，我們繼續(xù)對(duì)它進(jìn)行優(yōu)化，也就是我們繼續(xù)尋找隱性條件，其實(shí)對(duì)于定理一我們可以進(jìn)行這樣的推廣：這個(gè)子數(shù)組里的從第1項(xiàng)加到第n項(xiàng)的和必不小于0，即該子數(shù)組的前n項(xiàng)的和必大于0。稱(chēng)為定理二，證明不必了，跟定理一一樣。我們繼續(xù)增加這個(gè)條件，減少枚舉的次數(shù)：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

for(i=0;i<n;i++) { ???if(a[i]<0) ??????continue; ????temp=a[i]; ?????????????????if(temp>ans) ???????????????????????????????????ans=temp; ?????????????????for(j=i+1;j<n;j++) ?????????????????{ ??????????????????????????temp+=a[j]; ????????????????if(temp<0) ????????????????????{ ????????????????????????i=j; ????????????????????????continue; ????????????????????} ??????????????????????????if(temp>ans) ???????????????????????????????????ans=temp; ?????????????????} }

代碼運(yùn)算速度繼續(xù)得到加快，特別是當(dāng)temp<0時(shí)，i=j，直接跳過(guò)的不必要枚舉又有了很多，我們繼續(xù)想想還可以繼續(xù)優(yōu)化嗎？還有隱式條件嗎？我們繼續(xù)分析，不難得到這點(diǎn)，即我們得到最大值的那個(gè)數(shù)列必然滿(mǎn)足這點(diǎn)：在滿(mǎn)足定理二的條件下（滿(mǎn)足定理二必滿(mǎn)足定理一），盡可能多的數(shù)相加得到的值最大，這個(gè)顯而易見(jiàn)的，對(duì)于特定的數(shù)組，它的每個(gè)數(shù)都大于0的話(huà)，最大值子數(shù)列即它本身，即滿(mǎn)足當(dāng)前條件下盡可能多的數(shù)相加得到的值最大，這個(gè)隱式條件有什么用呢？根據(jù)它實(shí)際我們可知不必枚舉所有的子數(shù)組的值，我們只需枚舉可以去到最多的滿(mǎn)足條件的數(shù)的數(shù)組就可以求出最大值，根據(jù)這個(gè)我們只需這樣進(jìn)行一次枚舉即可：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

int qiuzhi(int n) { ?????????int i,ans,temp=0; ?????????ans=a[0]; ?????????for(i=0;i<n;i++) ?????????{ ?????????????????temp+=a[i]; ?????????????????if(temp>ans) ??????????????????????????ans=temp; ?????????????????if(temp<0) ??????????????????????????temp=0; ?????????} ?????????return ans; }

于是乎，我們的算法的時(shí)間復(fù)雜度從o(n^2)降到了o(n),優(yōu)化優(yōu)化再優(yōu)化，沖破單一暴力枚舉，你的能力得到提升。到了這樣速度已經(jīng)很好了，但是不要滿(mǎn)足不要逗留，就像浮士德的對(duì)逝去的瞬間發(fā)出的那句“逗留一下吧，你是那樣美！”，之后等待他的就是萬(wàn)劫不復(fù)的地獄。孜孜不倦的渴求，勇往直前的奮進(jìn)，才能讓人永遠(yuǎn)激昂，永遠(yuǎn)感受到青春的力量，永遠(yuǎn)立于不敗！

這樣之后，我們實(shí)際上還可以進(jìn)行優(yōu)化，精益求精，因?yàn)槎ɡ硪缓投ɡ矶梢赃@樣推廣：對(duì)于第一個(gè)數(shù)開(kāi)始，和最后一個(gè)數(shù)開(kāi)始同樣都是滿(mǎn)足的，所以?huà)呙杩梢詮膬深^同時(shí)開(kāi)始，這樣我們?cè)诓糠智闆r下可以節(jié)省部分時(shí)間，但是這么做造成了雙倍的空間，和幾個(gè)多出來(lái)的對(duì)中部的判斷情況進(jìn)行判斷，這樣又造成了額外的開(kāi)支，使這種優(yōu)化變得不必要。我嘗試了幾次對(duì)這個(gè)思路進(jìn)行特殊處理后來(lái)繼續(xù)優(yōu)化，但都失敗了，就不好意思把不成熟的代碼拿出來(lái)。

第二個(gè)問(wèn)題，是ustcoj上的1353切繩子，題目大意如下：開(kāi)始時(shí)你手上有一根長(zhǎng)為正整數(shù)N的繩子。你選擇一個(gè)長(zhǎng)度X(1 <= X <= N-1且為整數(shù))，將繩子切成長(zhǎng)為X和N-X兩部分，得到操作分(-X^2+N*X+K)。之后，你要在切出來(lái)的兩段繩子中選擇一段再做同樣的操作得到三段繩子。繼續(xù)下去，直到你得到N段長(zhǎng)為1的繩子為止（這時(shí)你無(wú)法再切下去了）。最終得分為你操作分的總和。如果每次切繩子時(shí)長(zhǎng)度X為隨機(jī)選擇的（等概率），手里有多段繩子時(shí)切的繩子也是從可以繼續(xù)切的繩子（長(zhǎng)度大于1）中隨機(jī)選擇的，那么最終得分的期望值是多少？（輸出結(jié)果只要整數(shù)部分）

初始解法，遞歸法暴力枚舉，解釋詳見(jiàn)注釋：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113

#include <stdio.h> float a[1001]={0};? //作為遞歸使用時(shí)加快遞歸算法速度的輔助儲(chǔ)存數(shù)組。 int b[1001]={0}; float f(int n)??? //計(jì)算當(dāng)前n下所有情況的總分 { ?????????int i; ?????????if(n>1) ?????????{ ?????????if(a[n]) ?????????????????return a[n]; ?????????else ?????????{ ?????????for(i=1;i<n;i++) ?????????????????{ ??????????????????????????a[n]+=n*i-i*i;??? //題目中的表達(dá)式 ??????????????????????????a[n]+=f(n-i)+f(i); ?????????????????} ?????????} ?????????return a[n]; ?????????} ?????????else ?????????????????return 0; } int h(int n)? //遞歸計(jì)算n下的總可能情況數(shù) { ?????????int i; ?????????if(n>2) ?????????{ ?????????if(b[n]) ?????????????????return b[n]; ?????????else ?????????{ ?????????????????for(i=1;i<n;i++) ??????????????????????????b[n]+=h(n-i)+h(i); ?????????????????return b[n]; ?????????} ?????????} ?????????else ?????????{ ?????????????????if(n==1) ?????????????????????return b[1]=0; ?????????????????else ??????????????????????????return b[2]=1; ?????????} } int main() { ?????????int n,k,s; ?????????float g; ?????????while(~scanf("%d %d",&n,&k)) ?????????{ ?????????????????s=h(n);?? //得到總的可能情況數(shù) ?????????????????g=f(n)/s+(n-1)*k;? //計(jì)算數(shù)學(xué)期望 ?????????????????printf("%.0f\n",g); ?????????} ?????????return 0; }

暴力枚舉沒(méi)任何技術(shù)含量，時(shí)間被大量的浪費(fèi)，且計(jì)算的過(guò)程會(huì)出現(xiàn)越界的情況，該代碼最多可以準(zhǔn)確的算到n=60左右，再大計(jì)算過(guò)程中a[n]里存儲(chǔ)的值超出float范圍，到后面long double也裝不下。于是繼續(xù)進(jìn)行分析,比如說(shuō)，對(duì)于求n下的總情況與n之間的函數(shù)關(guān)系是否可以求出來(lái)呢？這實(shí)際上就看你的高中的數(shù)列功底如何了，這兩個(gè)數(shù)學(xué)表述出來(lái)都是數(shù)列求通項(xiàng)的問(wèn)題。

求總的情況數(shù)：記為b數(shù)列，記第n項(xiàng)為bn,記前n項(xiàng)的和為Sn,求滿(mǎn)足以下條件的數(shù)列，b1=0,b2=1,

bn=(bn-1+b1)+(bn-2+b2)+…+(b2+bn-2)+ (b1+bn-1)??? ……?eq \o\ac(○,1)1

求通項(xiàng)：

bn=2Sn-1?????? ……?eq \o\ac(○,2)2

又因：bn=Sn-Sn-1? ……?eq \o\ac(○,3)3

由?eq \o\ac(○,2)2?eq \o\ac(○,3)3可得：Sn=3Sn-1為一等比數(shù)列。又S1=0，S2=1；所以有Sn=3n-3。

代入?eq \o\ac(○,2)2有：bn=2Sn-1=2*3n-3。

對(duì)于求總的得分?jǐn)?shù)有：同樣記為a數(shù)列，第n項(xiàng)為an，記前n項(xiàng)的和為Sn,求滿(mǎn)足以下條件的數(shù)列，a1=0,a2=1,

an=(an-1+a1+n*1-12)+(an-2+a2+n*2-22)+…+(a2+an-2+n*n-2-(n-2)2)+ (a1+an-1+n*n-1-(n-1)2)??? ……eq \o\ac(○,4)4

化簡(jiǎn)得到：Sn=3Sn-1+n*n+1*(n-1)/6?(可以左右兩邊同時(shí)加一個(gè)減一個(gè)，化成形如Sn+f(n)=3(Sn-1+f(n-1))這樣，化成一個(gè)等比數(shù)列了再求解，求出來(lái)后通式很復(fù)雜，不寫(xiě)出來(lái)了)，這個(gè)式子的通項(xiàng)很復(fù)雜，可以用左右兩邊加一個(gè)減一個(gè)方法化成等比數(shù)列，不過(guò)就算是求出來(lái)了，表達(dá)式過(guò)于恐怖了，不好寫(xiě)，于是求到這步就停止了，繼續(xù)用遞歸往下求就行了，雖然因?yàn)閿?shù)學(xué)不夠好求不下去了，但比之開(kāi)始又快了好多，代碼如下：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

#include <math.h> #include <stdio.h> double a[1001]={0}; double f(int n) { ?????????if(a[n]) ??????????????????return a[n]; ?????????else ?????????{ ?????????if(n>2) ?????????{ ??????????????????return a[n]=n*(n*n-1)/6+3*f(n-1); ?????????} ?????????else ??????????????????return 1; ?????????} } int main() { ?????????int n,k; ?????????double g; ?????????while(~scanf("%d %d",&n,&k)) ?????????{ ??????????????????if(n>2) ??????????????????{ ?????????????????????g=(f(n)-f(n-1))/(2*pow(3.0,n-3))+(n-1)*k; ??????????????????} ??????????????????else ??????????????????{ ??????????????????????????if(n==1) ???????????????????????????????????printf("0\n"); ??????????????????????????else ???????????????????????????????????g=k+1; ??????????????????} ??????????????????printf("%.0lf\n",g); ?????????} ?????????return 0; }

比開(kāi)始時(shí)代碼都精簡(jiǎn)了好多。

繼續(xù)代入，由于bn=2*3n-3，實(shí)際算出了求出來(lái)大概an的3n-3項(xiàng)系數(shù)大概在10*3n-3左右，其他部分在n>=5時(shí)an/bn都是小數(shù)，由于只要求輸出整數(shù)部分，所以在n>=5時(shí)可以取an/bn=5即可，對(duì)n<5時(shí)單獨(dú)列表繼續(xù)進(jìn)行簡(jiǎn)化；又g=an/bn+(n-1)*k=n*k-k+5。

有新的簡(jiǎn)化：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#include <stdio.h> int main() { ?????????int n,k; ?????????long long g; ?????????while(~scanf("%d %lld",&n,&k)) ?????????{ ??????????????????if(n>=5) ??????????????????????????g=n*k+5-k; ??????????????????else ??????????????????{ ??????????????????????????switch(n) ??????????????????????????{ ???????????????????????????????????case 0: ???????????????????????????????????case 1: ????????????????????????????????????????????g=0; ????????????????????????????????????????????break; ???????????????????????????????????case 2: ????????????????????????????????????????????g=k+1; ????????????????????????????????????????????break; ???????????????????????????????????case 3: ????????????????????????????????????????????g=2*k+3; ????????????????????????????????????????????break; ???????????????????????????????????case 4: ????????????????????????????????????????????g=3*k+4; ????????????????????????????????????????????break; ??????????????????????????} ??????????????????} ??????????????????printf("%lld\n",g); ?????????} ?????????return 0; }

現(xiàn)在算法直接變得與n無(wú)關(guān)了，也突破了暴力枚舉，沒(méi)辦法，要命的數(shù)學(xué)，數(shù)學(xué)使用好了，什么都能迎刃而解。上題是邏輯的突破，現(xiàn)在這題是數(shù)學(xué)，是運(yùn)算方法的突破。

第三題，是ustcoj上的1274題k_star風(fēng)波，題意表達(dá)成數(shù)學(xué)語(yǔ)言就是：把一個(gè)長(zhǎng)度為n的數(shù)組分為m份(m<n)，保證連續(xù)且不改變順序，使得這m個(gè)子數(shù)列和中的最大值在所有分法里面最小，輸出最小值，和該分法（方便這篇文章的抒寫(xiě)，省去這個(gè)要求）。數(shù)組里的元素全為正整數(shù)。

現(xiàn)在我只分析輸出最小值，實(shí)際加一個(gè)數(shù)組記錄分法就可以輸出了。

首先還是暴力枚舉，鑒于我寫(xiě)的代碼太長(zhǎng)，很占篇幅，枚舉就不直接放出來(lái)了，關(guān)于枚舉的優(yōu)化演變我在第一個(gè)問(wèn)題里面假設(shè)最簡(jiǎn)單的枚舉法，看這篇文章的人都會(huì)寫(xiě)。但是可以肯定暴力枚舉必然通不過(guò)，因?yàn)槭敲杜e次數(shù)是一個(gè)組合數(shù)C(m,n)，太占時(shí)間了。

于是我優(yōu)化出了一個(gè)最長(zhǎng)時(shí)間在o((n-m)*n),最短時(shí)間在o(n)的不穩(wěn)定算法。一樣的尋找隱式條件，從可能最小值入手，一個(gè)個(gè)判斷是不是可以成立，成立了即終止。首先可能的最小值是在該數(shù)列的最大值和最大值加它旁邊的小值，假設(shè)是a[k]，首先先用一個(gè)搜索算法這個(gè)搜索到這個(gè)a[k]的位置，然后判斷a[k+1]和a[k-1]的大小（假設(shè)a[k-1]更小），最小值取得的范圍在a[k]到a[k-1]之間，然后掃描一遍整個(gè)數(shù)組，看是否可以滿(mǎn)足這個(gè)范圍內(nèi)取得最小值，如果不滿(mǎn)足最小值取得的范圍就在a[k]+a[k-1]，比較a[k+1]和a[k-2]的大小（假設(shè)a[k+1]小），那么范圍在a[k]+a[k-1]+a[k+1]之間了，繼續(xù)掃描一遍整個(gè)數(shù)組，看能不能取得，不能繼續(xù)進(jìn)行以上步驟，一直進(jìn)行n-m次，這部分代碼如下：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

......//先用搜索算法找到數(shù)組最大值位置k temp=0,min=0,maxin=0,point=0,r=l=0，fenshu，zhongzhi;//? temp是記錄每個(gè)部分的，min記錄要輸出的值，maxin記錄取值范圍，point記錄a[k]這次是加還是減，r記錄加的值，l記錄減的值,fenshu記錄當(dāng)前已經(jīng)分出的份數(shù),zhongzhi用于判斷是滿(mǎn)足最小值范圍內(nèi)可以輸出，滿(mǎn)足則輸出最小值。 for(i=0;i<n-m;i++) { maxin=0; zhongzhi=1; ???if(point) ???{ ??????maxin+=a[k+r]; ??????????a[k+r]=0; ???} ???else ???{ ??????maxin+=a[k-l]; ???????????a[k-l]=0; ???} ???if(a[k+r+1]<a[k-l-1])??? //判斷a[k+r+1]和a[k-l-1]，確定k運(yùn)行的方向（是加還是減） ????{ ????????r++; ??????????point=1; ?????????} ???else ???{ ??????l++; ??????????point=0; ???} ???...... }

以上部分是掃描數(shù)組部分之前的代碼,for循環(huán)內(nèi)的省略部分代碼如下:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

fenshu=1;???? //初始就有包含a[k]的那份,所以fenshu=1; ???min=maxin;? ???for(j=0;j<n;j++) ???{ ??????if(a[j]==0)????? //跳過(guò)包含a[k]的那份，因?yàn)殚_(kāi)始時(shí)已計(jì)數(shù)。 ???????????{ ???????????????????????temp=0; ??????????????????fenshu++; ??????????????????j=k+r; ????????????????????????????continue; ???????????} ??????if(point)??????????????????? //判斷開(kāi)始k是加一，還是減一 ???????????{ ?????????????if(temp+a[j]<=maxin+a[k+g+1]) ??????????????????{ ?????????????????????temp+=a[j]; ?????????????????????if(temp>min) ?????????????????????min=temp; ??????????????????} ??????????????????else ??????????????????{ ??????????????????????temp=a[j]; ??????????????????????fenshu++; ??????????????????} ???????????} ???????????else ???????????{ ???????????if(temp+a[j]<=maxin+a[k-l-1]) ??????????????????{ ?????????????????????temp+=a[j]; ?????????????????????if(temp>min) ?????????????????????min=temp; ??????????????????} ??????????????????else ??????????????????{ ??????????????????????temp=a[j]; ??????????????????????????fenshu++; ??????????????????} ???????????} ???????????if(fenshu>m) //要使得滿(mǎn)足最小值在范圍內(nèi)，必需使分法數(shù)大于m則不成立退出 ???????????{ ??????????????zhongzhi=0; ???????????????????break; ???????????} ???} } ?if(zhongzhi)?? break;?? //fenshu<m的話(huà)即可以保證該使得最小值在范圍里的分法成立，即終止，不然增加范圍，開(kāi)始下次循環(huán)。

以上部分即優(yōu)化后的代碼主要部分，算法由單純的暴力枚舉變成有選擇性有條理的枚舉，讓一切井然有序，層層遞進(jìn)，算法變得更優(yōu)了。

思考解決方案，設(shè)計(jì)方案基本思路、解法、算法，用某種語(yǔ)言將頭腦里前兩步所構(gòu)建的算法表述出來(lái)，然后以此為基礎(chǔ)，一步步完善，精益求精，以求盡善盡美，堅(jiān)持不懈，就算路途中與千億次失敗相伴，成功也會(huì)最終慢慢光臨。雖然寫(xiě)的代碼還是很不好漏洞很多，但是從完全沒(méi)有頭緒，到用很拙劣的思路寫(xiě)出很拙劣的代碼，然后再到一步步的對(duì)它們企求精美，于是思路慢慢被打開(kāi)，走向一片廣闊的天地，不再受困于在狹縫里挖掘，自己也就收獲了很多，收獲更多的是一種感覺(jué)，這種感覺(jué)別人無(wú)法體會(huì)，完善到自己的極限后，海闊天空的感覺(jué)，一份領(lǐng)悟，這種領(lǐng)悟?qū)?huì)使人受益終生，這也就是編程之美。

謹(jǐn)以此文表達(dá)對(duì)孫老師，還有兩位助教給予的幫助的感謝。

總結(jié)

以上是生活随笔為你收集整理的最大字段和 冲出暴力枚举的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。