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