APP
題目:
給出長(zhǎng)度為 n? 的全排列 p , q ，還有一個(gè)由 p , q 組成的長(zhǎng)度為 2 × n 的 S 。
現(xiàn)在有一個(gè)空序列 R? ，每次可以從 p? 或 q 的開(kāi)頭取出一個(gè)數(shù)字并加到 R 的末尾，問(wèn)有多少種取法使得 R = S , n<=3e5
思路:
- 對(duì)于s 的一個(gè)位置, 就可能2個(gè)位置,來(lái)計(jì)算貢獻(xiàn),?
- dp[i][j],來(lái)表示種類數(shù), dp[i][j],可以用 i-1,j-1來(lái)分別得到
- 但是這個(gè)n太大了,不過(guò)他的遞推很有限制條件, 所以利用dfs來(lái)解決
?
本文摘自 ：https://www.cnblogs.com/
