1、神奇的K線杭州學軍中學 李宇亮背景我們先來看幾只股票一段時間的k線。都很相似？然后呢？它們都大漲了！神奇的K線題意簡述一般的K線與神奇的K線的差異度最小總修改代價整數序列a一般的K線整數序列p神奇的K線的漲跌修改方法修改a中任意元素，代價modify刪除a中任意元素，代價deleten1500100%n50060%n10030%樣例解釋0121610-999159991998-9934-100910146a:ai+1-ai:p999改成3，代價1將-999刪除，代價2總代價為3modify=1delete=2算法分析題目要求的即是用最小的代價將序列a改成a滿足所有的a

2、i+1-ai=pi。對于a中每個元素有3種決策：修改、刪除或保留它。至少有一個元素會被保留。算法1動態(tài)規(guī)劃fi,ja:a:ij1i-1j-11保留保留、刪除、修改最小代價算法1fi,j(i-j)個刪除代價最小修改最少保留最多=maxfi,j+1 | i i, jj, i-ji-j, 最多保留個數最小代價修改代價刪除代價定值算法1如何轉化為答案？Ans= 。a:a:ij11n刪除修改或i+1j+1j+n-idustbin保留修改刪除modifydelete+(n-i)* , (j-fi,j)*modify+(i-j)*deletefi,j個保留minminn1500100%n50060%n100

3、30%算法1時間復雜度O(n4)。需要優(yōu)化。算法分析fi,j確定a1a:a:ij11算法2fi,jfi,jfirsti,j=firsti,jfirsti,j不同的狀態(tài)分開DPO(n4)數形結合將f列成一個表格平行四邊形枚舉所有枚舉每一列76543217654321ijjji-ji-j無用的狀態(tài)正在計算的狀態(tài)fi,jii算法分析DP的順序。76543217654321ij算法3按斜線DP。用一個數組best記錄每一列的最優(yōu)狀態(tài)。將first不同的狀態(tài)分開算法3時間復雜度O(n3)。還需要優(yōu)化。n1500100%n50060%n10030%算法分析fi,j從best1到bestj-1中轉移連續(xù)的一

4、段。線段樹！=O(n3)O(n2)O(n)很難減少需要降低O(logn)O(n2logn)算法4按first分類按斜線順序DP：best1bestj-1fi,jfi,jbestj76543217654321ijbest:線段樹算法4時間復雜度O(n2log n)n1500100%n50060%n10030%Accepted小結確定狀態(tài)修改含義分開DP改變順序記錄最優(yōu)用線段樹問題解決抽象first數形結合測試測試結果如下：謝謝大家狀態(tài)的另一種表示fi,jj個留下（保留、修改），i-j個刪除gi,ji個刪除，j個留下。第(i+j)個保留狀態(tài)的另一種表示76543217654321ij7654321

5、7654321ij數據第一個數據是樣例再多加一個數第四個數據的p是1 -2 -3 4 -1 2 3 -4 這樣循環(huán)的，a中的都是09的隨機數。數據其他數據p的生成方式：先隨機生成序列A1.An，其中所有的Ai都只有少量的可能的取值。然后pi=Ai+1-Ai。a的生成方式：先隨機生成少量的數放在數組c中。對于每個ai，較大的概率取到c中的數，較小的概率為隨機數。惡搞都是將數列分成50個一段，每段之內DP，段與段之間直接貪心。第一種是多余的刪去第二種是多余的修改K線圖K線圖（Candlestick Charts）又稱蠟燭圖、日本線、陰陽線、棒線等，常用說法是“K線”，起源于日本十八世紀德川幕府時代（16031867年）的米市交易，用來計算米價每天的漲跌。因其標畫方法具有獨到之處，人們把它引入股票市場價格走勢的分析中，經過300多年的發(fā)展，已經廣泛應用于股票、期貨、外匯，期權等證券市場。 算法1fi,j=minfi,j 這里要求a:a:ij刪除、修改，有代價1i-1j-11iji+1j+1保留保留顯然ii,jj,i-ji-