首页 > 试题广场 >

序列组装

[编程题]序列组装
  • 热度指数：167 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
对于长度为n的字符串str[1..n]，假设1<=i,j<=n，定义str[1..i]为str的前缀，str[j..n]为str的后缀。
比如str="abcd"，则"a"、"ab"、"abc"和"abcd"都是"abcd"的前缀，"d"、"cd"、"bcd"和"abcd"都是"abcd"的后缀。
如果字符串str2的一个前缀刚好是str1的后缀，那么允许这两个字符串拼接，比如Xabc后面可以拼接上abcYZ
得到X[abc]YZ（中括号表示两个串重叠的部分）。现在给定一系列固定长度的字符串，求它们能拼接成的最短字符串。

举个例子，给定两个字符串ATCC和CCTA，它们可以拼接成ATC[C]CTA, AT[CC]TA, CCT[A]TCC，其中最短的字符串长度是6。

复杂度的说明： O(n^2*(2^n+L))可以通过所有数据。 其他的复杂度如果优化得当，也可以得分
时限维持1s

输入描述:
第一行一个正整数T，表示T个测试样例；
对于每个测试样例，
输入正整数n（n<=10）和l（l<=1e4），分别表示字符串个数n，以及字符串的长度l（字符串只包含数字和字母）；
接下来n行，输入n个字符串。


输出描述:
输出T行，每行一个正整数，表示每个样例能得到的最短拼接长度
示例1

输入

1
2 4
ATCC
CCTA

输出

6

备注:
有60%的数据满足 L<=100
算法知识视频讲解
开通博客
头像 肖战公关团队
发表于 2020-05-13 14:16:19
题解 要求复杂度在内，很显然这样的复杂度应该是用状压dp。 令表示已经放了的状态下，最后放入的是第个字符串的最小答案。（这里的下标从开始） 那么就有这样的状态转移： 首先如果状态中只有一个字符串，那么。（表示第个字符串的长度） 那么对于状态中不止有一个字符串的，且有的有： 这里表示的意思是当前是要 展开全文
去ta的博客 赞 (4) 回复(0) 收起

问题信息

C++工程师 深信服
来自：深信服校园招聘c/c ...
上传者：小小
难度：
0条回答 2415浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号