國(guó)家集訓(xùn)隊(duì)作業(yè)命題wqs

1、能量棒哈爾濱市第三中學(xué) 王欽石給定一個(gè)長(zhǎng)為N的正整數(shù)列A，分成K段，定義每段的價(jià)值為 x2+Bx+C，其中x為這一段的和，求最大的總價(jià)值。K=N=105題目大意記每段和為Si，則總價(jià)值為(-Si2+BSi+C)，可以變形為-Si2+BSi+CK = -Si2+BAi+CK，后兩項(xiàng)都是與決策無關(guān)的，所以只需求出Si2的最小值不經(jīng)這步簡(jiǎn)化，下述所有算法稍加修改均仍可用，不過編碼難度將有所增加以下將以求最小平方和為問題進(jìn)行求解分析枚舉分段方案，計(jì)算每個(gè)方案的答案，求最小值。時(shí)間復(fù)雜度：O(NK)期望得分：510分算法一顯然可以進(jìn)行動(dòng)態(tài)規(guī)劃記fij為將前i個(gè)數(shù)分成j段所能獲得的最小平方和，枚舉最后一段

2、的長(zhǎng)度進(jìn)行轉(zhuǎn)移轉(zhuǎn)移方程fij = minfkj-1+(Ak.i-1)2時(shí)間復(fù)雜度O(N3K)，期望得分15分可以使用前綴和快速計(jì)算出Ak.i-1時(shí)間復(fù)雜度O(N2K) ，期望得分2025分算法二轉(zhuǎn)移方程滿足四邊形不等式記pij為計(jì)算fij時(shí)取到最優(yōu)值的最小的k有pi-1jpij pij-1先計(jì)算fi-1j和fij-1，并記錄p值計(jì)算fij時(shí)只需檢查k在區(qū)間pi-1j, pij-1的情況即可對(duì)于每個(gè)x，所有i+j=x的fij只需檢查O(N)次時(shí)間復(fù)雜度O(N2)期望得分40分算法三記A中前i個(gè)數(shù)的和為Si轉(zhuǎn)移方程fij = minfkj-1+(Si-Sk)2變形為fij = minfkj-1+S

3、i2+Sk2-2SiSk按j從小到大計(jì)算，將每個(gè)fkj-1看做平面上一個(gè)點(diǎn)(Sk , fkj-1+Sk2)，每次找出y-2Six最小的點(diǎn)凸殼！O(N)掃描求出凸殼，由于S是遞增的，可以掃描一次求出每個(gè)i的答案時(shí)間復(fù)雜度O(NK)，期望得分50分算法四通過一些手段剪掉不優(yōu)的狀態(tài)，減小計(jì)算量缺點(diǎn)是時(shí)間復(fù)雜度/解的最優(yōu)性沒有保障得到高分需花費(fèi)較多時(shí)間較好情況下期望得分5080分非完美算法考慮這樣一個(gè)問題，把一個(gè)數(shù)列分成若干段(不限定段數(shù))，使平方和最小，但是每分一段需要額外C的代價(jià)，即每段的代價(jià)是x2+C使用動(dòng)態(tài)規(guī)劃，fi表示前i個(gè)數(shù)分若干段的最小總代價(jià)可以使用算法四中的方法進(jìn)行優(yōu)化時(shí)間復(fù)雜度O(N

4、)算法五當(dāng)C值增大時(shí)，最優(yōu)解的段數(shù)會(huì)減小二分！二分C的大小，動(dòng)態(tài)規(guī)劃求解時(shí)記錄最優(yōu)解分的段數(shù)找到合適的C值，計(jì)算出上述問題的答案減去CK即為原問題答案時(shí)間復(fù)雜度O(NlogC)期望得分100分算法五這里有一個(gè)問題C不存在怎么辦？為了解決這個(gè)問題，我們?cè)谇蠼夤潭–值的問題時(shí)需要找到最優(yōu)解中分段數(shù)最少的一個(gè)，這可以在動(dòng)態(tài)規(guī)劃過程中控制如果C取某一值時(shí)分段數(shù)過少，-1后又過多，那么直接取此C值的答案減CK算法五對(duì)于一個(gè)固定的數(shù)列A，不同K值時(shí)的答案記做ans(K)那么點(diǎn)(K, ans(K)會(huì)形成如下形態(tài)可以證明，不存在合適C值的點(diǎn)一定如箭頭所示即(K, ans(K)形成的點(diǎn)集是凸的算法五一年多前思考

5、斜率優(yōu)化的應(yīng)用注意到定義每段代價(jià)為x2+C，則C越大，所分的段數(shù)越少想到二分C來求解限制分段數(shù)的問題考慮不存在合適C值的情況證明(K,ans(K)形成的點(diǎn)集一定是凸的加一點(diǎn)小包裝：求解最大化-x2+Bx+C設(shè)置題目背景命題思路斜率優(yōu)化可以擴(kuò)展為更普通的單調(diào)性優(yōu)化所以可以把每一段的價(jià)值改為更為復(fù)雜的函數(shù)不過這樣僅僅是增大了問題的復(fù)雜程度盡量使問題簡(jiǎn)潔優(yōu)美，沒有這樣設(shè)計(jì)命題思路我寫了3個(gè)不同的生成器并用統(tǒng)一的接口來調(diào)用gen(int N, int v)N為序列的長(zhǎng)度，v為數(shù)值的期望genA為在1,2v-1中等概率選擇一個(gè)數(shù)genB為將每100個(gè)數(shù)分為一段，每段有50%的概率在1,v-1中隨機(jī)產(chǎn)生，50%的概率在v+1,2v-1中隨機(jī)產(chǎn)生genC為每個(gè)數(shù)有0.1%的概率在1,1001v-1中產(chǎn)生，否則在1,v-1中產(chǎn)生數(shù)據(jù)設(shè)計(jì)前10個(gè)測(cè)試點(diǎn)全部由genA生成其余10個(gè)有2個(gè)為ABB，2個(gè)ACC，其余為ABC命題時(shí)我曾考慮提供數(shù)據(jù)生成器供測(cè)試非完美算法，這樣區(qū)分度會(huì)更好無法阻止選手獲得輸入數(shù)據(jù)，沒有成功數(shù)據(jù)設(shè)計(jì)得分分布(NOI正式選手)得分分布(60人集訓(xùn)隊(duì)選手)感謝CCF給我提供這次的機(jī)會(huì)感謝父母對(duì)我的養(yǎng)育感謝張海峰老師對(duì)我的指導(dǎo)感謝兩位教練和多位大牛對(duì)我的幫助感謝學(xué)校對(duì)我的支持感謝謝謝大家歡迎提問記dij為f