F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 5454 >> 现代科技这么发达了吗
tangjz @ 2018-11-16 03:01:44
[ Quote ] [ Edit ] [ Delete ] 1#
https://www.sciencedirect.com/science/article/pii/030439759390200D

最短公共非子序列问题在字符集大小 >= 2 的时候好像一直是NP完全?这题能做?

zbw001 @ 2018-11-16 13:48:40
[ Quote ] [ Edit ] [ Delete ] 2#
这上面说的是给定L个序列吧
tangjz @ 2018-11-16 15:15:37
[ Quote ] [ Edit ] [ Delete ] 3#
上面说的是:给定一个字符集 Σ,和在这个字符集上的字符串集合 L,以及一个非负整数 k,在这个字符集构成的字符串里,确定是否存在一个长度不超过 k 的字符串使得它不是任何一个 L 中字符串的子序列(子序列可以不连续),这个问题在字符集大小不小于 2 时是 NP 完全的。
zbw001 @ 2018-11-16 16:30:12
[ Quote ] [ Edit ] [ Delete ] 4#
那大概是 |L| 个序列,指数上的可能是 |L|
[Top] [Previous Page] [Next Page]

HOME Back