POJ 1795 DNA Laboratory

题意：

给n个由A C T G组成的字符串。

要求用这些字符串拼接，（如果两个穿的前缀和后缀有相同的部分可以重合），要求拼接成的串

长度最短且字典序最小。

一直觉得是什么“字符串不会做系列”的难题，结果是一道状压DP+dfs

看到n=15这么灵性的数字应该要灵性一下的。。。

二进制状压一下

dp[state][j] 表示在state状态下，最前面的串是j的情况

然后需要预处理一下两个串拼接的时候增加的长度

dist[i][j] 表示把第i个串拼在第j个串前面增加的长度：也就是i串的长度减去i的后缀和j的前缀重合的长度

对于dfs回溯

在得到短长度，并且字典序在当前最小时，最前面的串j时，需要找第二个串，已经知道dp[all-state[j]][j]

那么枚举转移过来的情况找到满足dp值满足，并且拼接后字典序最小的（注意这里是要去拼接比较一下，因为直接比较可能把前缀就隐藏了，不是直接比较下一个串的字典序）

易错，还有一点在输入串后，要办能够直接有完全重合的串处理掉。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <queue>
  5 #include <vector>
  6 #include <algorithm>
  7 #include <stack>
  8 #include <set>
  9 #include <map>
 10 #include <math.h>
 11 #define pb push_back
 12 #define CLR(a) memset(a, 0, sizeof(a));
 13 #define MEM(a, b) memset(a, b, sizeof(a));
 14 #define fi first
 15 #define se second
 16 
 17 using namespace std;
 18 
 19 typedef long long ll;
 20 
 21 const int MAXN = 107;
 22 const int MAXV = 207;
 23 const int MAXE = 207;
 24 const int INF = 0x3f3f3f3f;
 25 
 26 int sz;
 27 char s[MAXN << 1][MAXN];
 28 char str[MAXN << 1][MAXN];
 29 int n;
 30 int state[27];
 31 int dp[67000 << 1][27];
 32 int dist[27][27];
 33 char anstr[MAXN*MAXN << 1];
 34 void deal()
 35 {
 36     for (int i = 0; i < sz; i++)
 37     {
 38         for (int j = 0; j < sz; j++)
 39         {
 40             if (i == j) continue;
 41             int len = min(strlen(s[i]), strlen(s[j]));
 42             for (int l = len; l >= 0; l--)
 43             {
 44                 char ss[MAXN];
 45                 strcpy(ss, s[j]);
 46                 ss[l] = '

相关推荐