題目是要求 長度=5 且 嚴格遞增 的子序列 數目。


先離散化,最多到 50000。


dp[i][j] 表示 長度為 i 時,數字 j 當結尾時的 遞增子序列 數目。


得到 dp[i][j] = sum{dp[i-1][1]~dp[i-1][j-1]}。


這樣的複雜度是 O(n^2),無法符合題目。


很顯然的,你取 sum 只會取 比你小的數字,所以可以用 bit 取sum。


總複雜度 O(5*n*lgn) = O(nlgn)。


我的code


http://codepad.org/XmGtKNQ3


p.s: 答案 高達22位,所以最後要大數加法。


       如果連 bit 的部分都用 大數 就會 TLE 掉= =。


 

文章標籤
創作者介紹
創作者 jghs1328 的頭像
jghs1328

jghs1328

jghs1328 發表在 痞客邦 留言(0) 人氣()