Two Permutations (DP搜索的方式) (2022杭電多校3)
2022-09-06 22:48:32

題目:

給出長(zhǎng)度為 n? 的全排列 p , q ，還有一個(gè)由 p , q 組成的長(zhǎng)度為 2 × n 的 S 。
現(xiàn)在有一個(gè)空序列 R? ，每次可以從 p? 或 q 的開頭取出一個(gè)數(shù)字并加到 R 的末尾，問有多少種取法使得 R = S , n<=3e5

思路:

• 對(duì)于s 的一個(gè)位置, 就可能2個(gè)位置,來計(jì)算貢獻(xiàn),?
• dp[i][j],來表示種類數(shù), dp[i][j],可以用 i-1,j-1來分別得到
• 但是這個(gè)n太大了,不過他的遞推很有限制條件, 所以利用dfs來解決

?