题意:给出两个01串,找出一个最短的、保证不是给出的两个01串子序列的最短01串。
题解:

  • 如果是求一个序列的最短非子序列长,我们直接按照http://47.106.118.63/wp-admin/post.php?post=851&action=edit的方法即可。
  • 但是本题要求求两个01串,那么这种方法就不适用了
  • 刚刚看了一下,ac代码看不到,但是长度可以看到,3000+的长度,估计是自动机啥的,先略过。
  • 网上看到一个做法:
    • 解法:求出每个序列的每个位置后的第一个0,1的位置
      dp[i][j][0/1]表示,在第一个序列的x位置和在第二个序列的y位置后,填上0/1是否满足非公共子序列 dp[i][j][0/1]表示,在第一个序列的x位置和在第二个序列的y位置后,填上0/1是否满足非公共子序列
      dp[i][j][0/1]表示,在第一个序列的x位置和在第二个序列的y位置后,填上0/1是否满足非公共子序列
    • 但是没有想明白如何判断是否满足这个操作

发表评论

邮箱地址不会被公开。 必填项已用*标注