※ 引述《DJWS (...)》之銘言： : 這樣問或許很突兀 : 但我很想知道針對每個query 時間複雜度為O(n*d)的解法 : 可以教我嗎? :p #(L=n,H=d) = #(L=n,H>=d) - #(L=n,H>=d-1) 為了估計 #(L=n,H>=d), 把每一個滿足 (L=n,H>=d) 的序列, 作一些手腳: 因為它滿足 H>=d, 所以這一個序列一定在某一個 '(' 的時候, 第一次達到 H=d, 那麼就把從這一個 '(' 之後的每一個 '(' 和 ')' 的方向顛倒過來. 如果說 '(' 增加高度, ')' 降低高度, 原本的序列在結束的時候高度應該回到 0; 而這個動了手腳的序列, 在結束的時候, 高度就應該是 d-(-d) = 2d, 因為不動的部分高度是 d, 而動了的部分原本是要把高度減 d 的, 現在顛倒了就變成增加 d. 再回頭看一下我們動了怎樣的手腳.. 原本在 (L=n,H>=d) 裡的序列, 就是說: 1.這個序列的最高處 高度 >= d, 2.這個序列的高度處處 >= 0, 3.這個序列的高度最後回到 0. 那動了手腳以後, 就是: 1a.這個序列的高度在達到 d 之前, 處處 >= 0, 2a.這個序列的高度在達到 d 之後, 處處 <= 2d, (等價於處處 <= 2d) 3a.這個序列的高度最後到 2d. 原本最高處高度 >= d 這個條件不需要了, 因為這個序列的高度最後會到 2d, 表示它一定會經過高度 = d 的地方, 從一次達到 d 的地方開始把往後的 '(' ')' 顛倒就會得到原本最高處高度 >= d 這個條件的序列; 而序列的高度處處 <= 2d, 是因為如果它有的地方高度 > 2d, 那麼折下來以後就會跑到高度 < 0 的地方; 然後序列的高度在達到 d 之後可以 < 0, 是因為它在顛倒後只是原序列高度 > 2d 的地方. 可以驗證一下, 這剛好是充要條件. 只考慮條件 3a. 的序列共有 C(n, 0.5n+d) 個, 因為: #'(' + #')' = n, 而且 #'(' - #')' = 2d, 所以 #'(' = 0.5n+d, #')' = 0.5n-d 而滿足條件 3a. 卻砥觸 2a. 的序列, 我們估計一下.. 在這種序列達到 2d+1 之後, 把在這個 '(' 後面的所有括號都顛倒過來, 這種序列只需要滿足: 高度最後到 2d+1 - (-1) = 2d+2 所以這種序列共有 C(n, 0.5n+2d+2) 個. 而對於滿足條件 2a. 和 3a. 序砥觸 1a. 的序列, 用白話講這樣的序列, 就是它的高度不會超過 2d, 並且最後會停在 2d, 而在達到 d 之前, 就曾走到 -1 了. 從第一次到達 -1 的 ')' 開始, 把之後的 '(' 和 ')' 倒過來, 所成的新序列會滿足: 1b. 結束時高度會停在 -1 - ( 1 + 2d ) = -2d-2, 2b. 高度處處 < d, 3b. 高度處處 >= -2d-2. 其中 2b. 是反應在走到 -1 之前沒有達到 d; 3b. 是反應原本的處處 <= 2d. 滿足 1b. 的序列有 C(n, 0.5n-2d-2) 個. 滿足 1b. 卻砥觸 2b. 的序列.. (類似滿足 3a. 砥觸 2a. 的情形) 有 C(n, 0.5n+4d+2) 個. 滿足 1b. 和 2b. 卻砥觸 3b. 的序列.. (作類似之前的變換) 就如同滿足下列條件的新序列: 1c. 結束時高度會停在 -2d-4, 2c. 高度在達到 -2d-3 以後, 處處 > -5d-6 (就是處處 > -5d-6), 3c. 高度在達到 -2d-3 以前, 處處 < d. 滿足 1c. 的有 C(n, 0.5n-2d-4), 滿足 1c. 卻砥觸 2c. 的序列有 C(n, 0.5n-8d-8), 滿足 1c. 和 2c. 卻砥觸 3c. 的序列, 就像滿足: 1d. 結束時高度會停在 4d+4, 2d. 高度處處 > -2d-3, 3d. 高度處處 < 6d+6. 滿足 1d. 的有 C(n, 0.5n+4d+4), 滿足 1d. 卻砥觸 2d. 的序列有 C(n, 0.5n-8d-10), 滿足 1d. 和 2d. 卻砥觸 3d. 的序列, 就像滿足: 1e. 結束時高度會停在 8d+8, 2e. 高度在達到 6d+6 以後, 高度處處 < 14d+15 (就是處處 < 14d+15), 3e. 高度在達到 6d+6 以前, 處處 > -2d-3. 滿足 1e. 的有 C(n, 0.5n+8d+8) 個, 滿足 1e. 砥觸 2e. 的有 C(n, 0.5n+20d+22) 個, 滿足 1e. 2e. 砥觸 3e. 的, 就像: 1f. 結束時停在 -12d-14, 2f. 高度處處 < 6d+6, 3f. 高度處處 > -18d-21. ... 一旦 0.5n+?d+? 這東西會超過 n 或小於 0, 這計算就停止了. 所以一定不會超過 O(n) (有可能 O(log n) ) 而這些瑣瑣碎碎的 a→b→c→d→e→f→... 是可以寫個函數把它們的關係寫出來的 b,d,f,... 情形比較類似, a,c,e,... 比較類似, 可以分成兩個函數寫, 也可以分成四個 (如果想把正負號不同的放在不同的函數的話) 再觀察一下, 無果在討論 b→c, d→e, ... 的時候換一下 2 和 3 的順序, 似乎可以單純化為兩個函數就好. 最後, 對於用到的 C(n,?) 若用 Pascal 三角形法來算, 把用到的都求出來, 總共也是花 O(n*d) 的時間. --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.42