題目網址: http://goo.gl/YH2Vad
題意: 有個序列正整數的特質為k在序列中會出現連續f(k)次，還是直接看題目好了解....，然後題目要求f(n)，1 <= n <= 2000000000。
解法:由於n會到2000000000，所以應該不可能直接開個陣列模擬巴...，要解這題要先定義另一個數列 s，滿足 s(x) 為 f 數列中 f(t) = x 且 t 盡量大，舉 s 數列的前幾項， s(1) = 1, s(2) = 3, s(3) = 5, s(4) = 8, s(5) = 11...，如果看題目的附表應該能很快理解，接著要可以推出 s(n) 的算法為 s(n) = s(n-1) + f(n) ，而獲得 s 數列後，就可以推出 f(n) = k, s(k) > n 且 k 盡量小，只要求出所需的 s 數列，以 binary search 在 s 數列找出滿足條件的 lower bound 即可，而藉由題目的測資，可以慢慢估出 s 數列只需要求到約 700,000 ，就可以推出長度為2*10^9的 f 數列了，而 s(n) 可以由下往上的方式遞推出來，可以勉強算是DP巴。
TAG: DP, binary search
注意:
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽