Java教程

Two Permutations (DP搜索的方式) (2022杭电多校3)

本文主要是介绍Two Permutations (DP搜索的方式) (2022杭电多校3)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目:

给出长度为 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来解决

 

这篇关于Two Permutations (DP搜索的方式) (2022杭电多校3)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航