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

題目:

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

思路:

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

?