Time Limit: 5000MS | Memory Limit: 30000K | |
Total Submissions: 1425 | Accepted: 280 |
Description
Having started to build his own DNA lab just recently, the evil
doctor Frankenstein is not quite up to date yet. He wants to extract his
DNA, enhance it somewhat and clone himself. He has already figured out
how to extract DNA from some of his blood cells, but unfortunately
reading off the DNA sequence means breaking the DNA into a number of
short pieces and analyzing those first. Frankenstein has not quite
understood how to put the pieces together to recover the original
sequence.
His pragmatic approach to the problem is to sneak into university
and to kidnap a number of smart looking students. Not surprisingly, you
are one of them, so you would better come up with a solution pretty
fast.
Problem
You are given a list of strings over the alphabet A (for adenine), C
(cytosine), G (guanine), and T (thymine),and your task is to find the
shortest string (which is typically not listed) that contains all given
strings as substrings.
If there are several such strings of shortest length, find the smallest in alphabetical/lexicographical order.
Input
For each scenario, the first line contains the number n of strings
with 1 <= n <= 15. Then these strings with 1 <= length <=
100 follow, one on each line, and they consist of the letters "A", "C",
"G", and "T" only.
Output
output for every scenario begins with a line containing "Scenario #i:",
where i is the number of the scenario starting at 1. Then print a
single line containing the shortest (and smallest) string as described
above. Terminate the output for the scenario with a blank line.
Sample Input
1
2
TGCACA
CAT
Sample Output
Scenario #1:
TGCACAT
Source
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define maxn 105 #define INF 10000 int n,ca,len,sum;
char s[][maxn];
int dp[][( << ) + ],dis[][];
bool vis[],done[];
string ans; int cal(int x,int y) {
int _max = ;
for(int i = ; i < strlen(s[x]); i++) {
if(s[x][i] != s[y][]) continue;
int j,k;
for( j = i,k = ; j < strlen(s[x]) && k < strlen(s[y]); j++,k++) {
if(s[x][j] != s[y][k]) break;
}
if(k == strlen(s[y])) {
done[y] = ;
break;
}
if(j == strlen(s[x])) {
_max = max(_max,j - i); }
} return -_max;
}
void init() {
for(int u = ; u < n; u++) {
if(done[u]) continue;
for(int v = ; v < n; v++) {
if(u == v || done[v]) continue;
dis[u][v] = cal(u,v); }
} } void dfs(int v,int s1) {
vis[v] = ;
int id = -;
string t("z");
for(int u = ; u < n; u++) {
if(done[u] || vis[u]) continue; if(dp[v][s1] == dp[u][s1 | ( << u)] + dis[v][u]) {
string t1(s[u] - dis[v][u],s[u] + strlen(s[u]));
if(t > t1) {
t = t1;
id = u;
}
} } if(id != -) {
ans = ans + t;
dfs(id,s1 | ( << id)); }
} void solve() {
init(); for(int s1 = ( << n) - ; s1; s1--) {
for(int v = ; v < n; v++) {
if(!(s1 & ( << v)) || done[v]) continue;
for(int u = ; u < n; u++) {
if(u == v || (s1 & ( << u)) || done[v] ) continue;
dp[v][s1] = min(dp[v][s1],dp[u][s1 | ( << u)] + dis[v][u]); }
}
} int _min = ;
for(int i = ; i < n; i++) {
if(done[i]) continue;
_min = min(_min,dp[i][ << i]);
} memset(vis,,sizeof(vis)); ans = "z";
int id;
for(int i = ; i < n; i++) {
if(done[i]) continue;
string t(s[i]);
if(dp[i][ << i] == _min && ans > t) {
ans = t;
id = i;
}
} dfs(id, << id); printf("Scenario #%d:\n",ca++);
cout << ans << endl; }
int main()
{
int t;
//freopen("sw.in","r",stdin);
scanf("%d",&t);
ca = ; while(t--) {
memset(done,,sizeof(done)); scanf("%d",&n); for(int i = ; i < n; i++) {
scanf("%s",s[i]);
} memset(dis,,sizeof(dis)); for(int i = ; i < n; i++) {
for(int s = ; s < ( << n); s++) {
dp[i][s] = ;
}
} solve();
printf("\n"); } return ;
}
POJ 1795的更多相关文章
-
POJ 1795 DNA Laboratory(状压DP)
[题目链接] http://poj.org/problem?id=1795 [题目大意] 给出n个字符串,求一个最小长度的串,该串包含给出的所有字符串. 要求长度最小且字典序最小. [题解] dp[i ...
-
POJ 1795 DNA Laboratory (贪心+状压DP)
题意:给定 n 个 字符串,让你构造出一个最短,字典序最小的字符串,包括这 n 个字符串. 析:首先使用状压DP,是很容易看出来的,dp[s][i] 表示已经满足 s 集合的字符串以 第 i 个字符串 ...
-
poj 1795 DNA Laboratory
DNA Laboratory Time Limit: 5000MS Memory Limit: 30000K Total Submissions: 2892 Accepted: 516 Des ...
-
POJ 3370. Halloween treats 抽屉原理 / 鸽巢原理
Halloween treats Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 7644 Accepted: 2798 ...
-
POJ 2356. Find a multiple 抽屉原理 / 鸽巢原理
Find a multiple Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 7192 Accepted: 3138 ...
-
POJ 2965. The Pilots Brothers&#39; refrigerator 枚举or爆搜or分治
The Pilots Brothers' refrigerator Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 22286 ...
-
POJ 1753. Flip Game 枚举or爆搜+位压缩,或者高斯消元法
Flip Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 37427 Accepted: 16288 Descr ...
-
POJ 3254. Corn Fields 状态压缩DP (入门级)
Corn Fields Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 9806 Accepted: 5185 Descr ...
-
POJ 2739. Sum of Consecutive Prime Numbers
Sum of Consecutive Prime Numbers Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 20050 ...
随机推荐
-
项目游戏开发日记 No.0x00000
14软二杨近星(2014551622) ---恢复内容开始--- 2016-03-17 从开始迈进软件工程专业, 已经快两年了, 记得当初选择软件的理由是, 我要学去做东西, 我享受开发过程. 两年来 ...
-
安裝 14.04.1 Ubuntu 到 Lenovo thinkpad t460p
在 Lenovo Thinkpad T460p 安裝 ubuntu, BIOS 需要做一些設定, 沒設定的現象:不斷地停在 usb disk 設定 可以 使用 usb disk install 了!
-
Java获取Web服务器文件
Java获取Web服务器文件 如果获取的是服务器上某个目录下的有关文件,就相对比较容易,可以设定死绝对目录,但是如果不能设定死绝对目录,也不确定web服务器的安装目录,可以考虑如下两种方式: 方法一: ...
-
解决父类加载iframe,src参数过大导致加载失败
原文:解决父类加载iframe,src参数过大导致加载失败 <iframe src="*******.do?param=****" id="leftFrame&qu ...
-
.NET 中文转缩写拼音
public class CNToSpell { /// 汉字转拼音缩写 /// Code By MuseStudio@hotmail.com /// 2004-11-30 /// 要转换的汉字字符串 ...
-
SQLServer2005 提示 &#39;其他会话正在使用事务的上下文&#39;
MSDN上看了一下说是sql server 2005不支持在分布式事务处理中存在指向本地的链接服务器(环回链接服务器) 这个是官方的回答 个人认为,应该是在事务中,使用了链接服务器访问进行跨库访问引起 ...
-
move_uploaded_file的failed to open stream错误处理
PHP的基本语法学习的差不多了,现在开始学习PHP的文件上传功能实现了.功能中使用到了move_uploaded_file方法,运行时报错: failed to open stream. 经过查资料, ...
-
Leetcode#191. Number of 1 Bits(位1的个数)
题目描述 编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 '1' 的个数(也被称为汉明重量). 示例 : 输入: 11 输出: 3 解释: 整数 11 的二进制表示为 000000 ...
-
监控SQLServer作业执行情况脚本
SELECT [sJOB].[job_id] AS [作业ID] , [sJOB].[name] AS [作业名] , CASE WHEN [sJOBH].[run_date] IS NULL OR ...
-
orcale 闪回操作 已提交的修改 给还原
delete from conf_ty_parser_title; INSERT INTO conf_ty_parser_title ( SELECT * FROM conf_ty_parser_ti ...