※ 引述《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