POJ 1795 DNA Laboratory

admin · 发表于 2018-9-3 17:47:30

题意：给出N个字符串，寻找一个字符串使得这N个字符串都是它的子串。输出最短的满足要求的串，如果有多个最短，输出字典序最小的 len<=100 n<=15

admin · 发表于 2018-9-3 17:47:47

预处理把j号串拼在i号串前面所增加的长度
（如aab拼在bca前增加长度为2）
d(S,i)表示目前答案串包含集合为S，最前面的是i号串
d(S+j,j)=d(S,i)+cost[i][j]

		自动登录	找回密码
密码			立即注册