國家集訓隊作業(yè)命題wqs

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

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

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

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

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