集訓(xùn)隊(duì)作業(yè)-一類動(dòng)態(tài)優(yōu)化

一類動(dòng)態(tài)規(guī)劃問題的優(yōu)化方廣西柳州鐵路第一中學(xué)林濤【看看的解題報(bào)告。【正文】歐元問題描述：給一數(shù)列a1、a2、…、an和T，要求把數(shù)列劃分成若干段，每段有一個(gè)權(quán)值F，如將ai、…、aj分為一段，則該段權(quán)值計(jì)算如下：jFSum[i,jjT，其中Sum[i,jk其中1n34567，并且1000ai1000(i1,2,...,n。F[i]i項(xiàng)的最優(yōu)劃分權(quán)值和，t[i]為數(shù)列前i項(xiàng)之和，則F[iMax{F[kt[it[ki 0k邊界條件：F[0]=0整個(gè)算法的時(shí)間復(fù)雜度 O(n2)。能否進(jìn)一步優(yōu)化首先對(duì)數(shù)列最優(yōu)劃分方案進(jìn)行分設(shè)有某段數(shù)列：ai、…、

j<n如果存ikj，使得ai、…、ak-1之和為負(fù)，ak、…、aj之和為正，那么分一定不是最優(yōu)的。因?yàn)榭梢栽诒３制渌鼊澐植蛔兊那闆r下，將ai、…、ak-1獨(dú)立出來，而ak、…、aj并入下一個(gè)劃分的數(shù)列，這樣，ai、…、ak-1所乘的數(shù)變小，ak、…、aj所乘的數(shù)就變大了，總權(quán)值就變大了。因此有這樣的結(jié)論：如果ai、…、aj（<n）是最優(yōu)劃分方案中的子方案，那么必定有：t[j][i-]，使得劃分更優(yōu)。S[ki]F[k(t[it[kiT，則對(duì)于任意0k1k2iS[k1,i]F[k1](t[i]t[k1])iT,S[k2,i]F[k2](t[i]t[k2])iS[k1,i]S[k2,i]F[k1]F[k2](t[k2]t[k1])可以知道ak11...ak2的和為正，所以無論數(shù)列a1...ak2如何劃分，都必然2當(dāng)t[k2t[k1]時(shí)若S[k1,iS[k2iF[k1F[k2t[k2t[k1i即iF[k2F[k1t[k1]t[k則對(duì)于任意ji，有S[k1jS[k2j0，令g(j,k)=(F[k]-F[j])/(t[j]-t[k])對(duì)于0<k1<k2<k3<…<kn，可以一個(gè)隊(duì)列，使得t[k1]>t[k2]>t[k3]>…>t[kn]，保證：ig(k2,k1)g(k3,k2)g(k4,k3)...g(kn,kn那么有S[k1i]S[k2i]S[k3,i]S[kni。則F[i]F[k1](t[i]t[k1])i。實(shí)現(xiàn)（1）加入一個(gè)新元素k。因?yàn)閗>kn，所以把k放置于隊(duì)列尾，若g(kkn)g(knkn1)，則nn1g(knkn1)g(kkn)（2）g(k2,k1)i，k1g(k2,k1)i最大平均數(shù)問題描述：給一數(shù)列a1，a2，…，an，求長(zhǎng)度至少為L(zhǎng)的一段，使這其平均數(shù)最大。析aiF[i]F[i+1]<F[i]F[i+1]F[i]-1F[i]i+1F[i+1]F[i]-1F[i]i的平均由以上的結(jié)論，在計(jì)算最大平均數(shù)時(shí)，只需關(guān)心當(dāng)F[i+1]>=F[i]時(shí)，以i+1為結(jié)尾的序列的平均數(shù)即可。pp、p+1、p+2…的平均數(shù)分別x0、x1、x2…，xi>xi+1，pp+ip+i+1p+i+1p+i+2xi>xi+1的現(xiàn)象，所以一個(gè)序列P1，P2，P3，xi為PiPi+1-1的平均數(shù)，使他們滿x1<x2<x3<x4<…。由于可刪除的序列不得超過i-L，所以當(dāng)i增大時(shí)，可刪除的序列會(huì)增加，當(dāng)序列增加時(shí)，就需要維PnPn+1-1的序列并Pn-1Pn-1的序列Pn刪除，反復(fù)進(jìn)的復(fù)雜度為O(n)。新型計(jì)算機(jī)問題描述：給了一個(gè)序列，要求更改序列后滿足：從序列第一個(gè)數(shù)開始，讀入一個(gè)數(shù)iijj分析：初次讀完題目，很容易想到動(dòng)態(tài)規(guī)劃的方程，令F[i]為從i開始恰好讀k令S[ik]F[k]|aii1k|，如果對(duì)于kj有：S[ikS[i,j]，則|aii1k||aii1j|F[j] 這個(gè)不等式的解集可能為ai+i+1<x。由這個(gè)單調(diào)性，試著像前兩題樣構(gòu)造序列k1>k2>k3S[nki1S[nki的解集為ai+i+1<xijai+i+1<xjkjk2，k3，…是不斷增加的，增加一個(gè)元素