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

题目:

给出长度为 n  的全排列 p , q ，还有一个由 p , q 组成的长度为 2 × n 的 S 。
现在有一个空序列 R  ，每次可以从 p  或 q 的开头取出一个数字并加到 R 的末尾，问有多少种取法使得 R = S , n<=3e5

思路:

• 对于s 的一个位置, 就可能2个位置,来计算贡献, 
• dp[i][j],来表示种类数, dp[i][j],可以用 i-1,j-1来分别得到
• 但是这个n太大了,不过他的递推很有限制条件, 所以利用dfs来解决