多邊形直徑問題

解題報(bào)告by湯周文N06032009012What?（建立模型）題目要求的是：對(duì)于一組給定的數(shù)組，因?yàn)長(zhǎng)是各邊的長(zhǎng)之和，所以大小是固定的，所以問題轉(zhuǎn)化為求也就是求給定數(shù)組的最接近l/2(有可能是*.5的形式)的連續(xù)子段和。如果我們把各個(gè)邊乘以2，就轉(zhuǎn)化為求給定數(shù)組的最接近L(整數(shù))的連續(xù)子段和。3How?（算法設(shè)計(jì)）(1)一看到題目，我們很自然有想把所有的可能都窮舉出來(lái)的做法的沖動(dòng)，這個(gè)算法很容易理解和編寫，但是這樣做的話，復(fù)雜度為o(N^2)。不符合題目的要求。如何改進(jìn)？上面的算法主要是沒有利用之前得到的信息，忘記歷史必將受到懲罰^_^。這題其實(shí)是由最大連續(xù)子段和問題遺傳和變異而來(lái)的。因此我們可以類似的引進(jìn)DP思想來(lái)解決，DPisthekey-_-。4How?（算法設(shè)計(jì)）(2)要在a0a1……

an-1序列求出最接近L的連續(xù)子段和。我們用兩個(gè)位置指針i和j，從i=0;j=0;開始，求得ai

ai+1……

aj之和t跟L的絕對(duì)差。繼而求ai

ai+1……

aj

aj+1之和(t+aj+1)，看t+aj+1跟L絕對(duì)差是否更小。更小則繼續(xù)(j++；)。否則求

ai+1……

aj-1之和(t-aj-ai)(i++;j--;)與L進(jìn)行比較后繼續(xù)，直至i=n時(shí)結(jié)束。為了不崩潰我們加入一個(gè)an=0，j就不會(huì)越界。

5算法流程圖6InputAndInitialization

while(scanf("%d",&n)!=EOF) {

int*edge=newint[n+1]; l=0;

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

scanf("%d",&edge[i]);//Hugeinput,scanfrecommended! l+=edge[i];

edge[i]*=2;//各個(gè)邊長(zhǎng)乘2便于計(jì)算

}

edge[n]=0; n++;i=0;j=1;//initt=edge[0];//init minimum=Abs(l-t);//init,minimum用來(lái)存放7MainProcess

while(i<n) {

if(Abs(l-(t+edge[j]))<Abs(l-t)) {/*如果從i到j(luò)+1的子段和更接近l*/ t+=edge[j];/*子段和加edge[j]*/ j++;/*j前進(jìn)一步*/

if(minimum>Abs(l-t))/*是否更接近*/ minimum=Abs(l-t); } else/*i前進(jìn)一步j(luò)退一步*/ { t-=(edge[i]+edge[j-1]); i++; j--;

if(minimum>Abs(l-t))/*是否更接近*/ minimum=Abs(l-t); } }

8Why?（算法分析）1.正確性：因?yàn)槲覀儧]有計(jì)算的連續(xù)子段都是有比它更優(yōu)的連續(xù)子段和存在，所以我們可以保證能夠得到最接近L的子段和。2.有效性：在整個(gè)算法的執(zhí)行過程中，數(shù)據(jù)的輸入需要的時(shí)間為o(n)，i