华师一附中OI组

标题: POJ 1795 DNA Laboratory [打印本页]

作者: admin 时间: 2018-9-3 17:47
标题: POJ 1795 DNA Laboratory
题意：给出N个字符串，寻找一个字符串使得这N个字符串都是它的子串。输出最短的满足要求的串，如果有多个最短，输出字典序最小的 len<=100 n<=15

作者: admin 时间: 2018-9-3 17:47
预处理把j号串拼在i号串前面所增加的长度
（如aab拼在bca前增加长度为2）
d(S,i)表示目前答案串包含集合为S，最前面的是i号串
d(S+j,j)=d(S,i)+cost[i][j]

欢迎光临华师一附中OI组 (http://hsyit.cn/)