Fun Game
https://odzkskevi.qnssl.com/8d698323a1e07d605cdeea708ee8a01d?v=1508703139
【题解】
不难发现如果一个串的原串或反转串是另一个串的子串，那么这个串是没有用的
我们把他剔除出去
如果此时只有一个串，暴力枚举解检查即可（网上很多写法是KMP。。不是很明白，没仔细看他们代码
多个串则状压DP
dp[s][i][0/1]表示s串已经选了，最后一个串是i，i是正着/倒着的，最大重叠字母数
刷表法转移即可
如何处理圈？我们强行在第一个串的地方断开，按照第一个串的正着的方向为圈的传递方向即可，
最后的时候枚举最后一个串跟第一个串交一下算答案
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #define min(a, b) ((a) < (b) ? (a) : (b)) 8 #define max(a, b) ((a) > (b) ? (a) : (b)) 9 10 inline void swap(int &a, int &b) 11 { 12 long long tmp = a;a = b;b = tmp; 13 } 14 15 inline void read(int& x) 16 { 17 x = 0;char ch = getchar(), c = ch; 18 while(ch < '0' || ch > '9')c = ch, ch = getchar(); 19 while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar(); 20 } 21 22 const int INF = 0x3f3f3f3f; 23 const int MAXN = 20; 24 const int MAXNUM = 1000; 25 26 int dp[(1 << MAXN) + 10][MAXN + 5][2], die[MAXN][2][MAXN][2], n, ma, sum, len[MAXN], cnt[MAXN], tot, b[MAXN]; 27 char s[MAXN][MAXNUM]; 28 29 inline void init() 30 { 31 memset(dp, 0, sizeof(dp)); 32 memset(die, 0, sizeof(die)); 33 tot = 0; 34 sum = 0; 35 memset(b, 0, sizeof(b)); 36 memset(len, 0, sizeof(len)); 37 memset(cnt, 0, sizeof(cnt)); 38 //check j是否包含在i中 39 for(register int i = 1;i <= n;++i) 40 { 41 scanf("%s", s[i] + 1); 42 len[i] = strlen(s[i] + 1); 43 } 44 for(register int i = 1;i <= n;++ i) 45 for(register int j = 1;j <= n;++ j) 46 { 47 if(i == j || b[i] || b[j] || len[j] > len[i])continue; 48 //正着配 49 for(register int a = 1;a <= len[i] - len[j] + 1;++ a) 50 { 51 int tmp1 = a; 52 while(s[i][tmp1] == s[j][tmp1 - a + 1] && tmp1 - a + 1 <= len[j]) ++ tmp1; 53 if(tmp1 - a + 1 > len[j]) b[j] = 1; 54 } 55 //倒着配 56 for(register int a = len[i];a >= len[j];-- a) 57 { 58 int tmp1 = a, p = 1; 59 while(s[i][tmp1] == s[j][p] && p <= len[j]) -- tmp1, ++ p; 60 if(p > len[j]) b[j] = 1; 61 } 62 } 63 for(register int i = 1;i <= n;++ i) 64 if(!b[i]) 65 cnt[++ tot] = i, sum += len[i]; 66 //j跟在i后面重叠部分大小 67 for(register int p = 1;p <= tot;++ p) 68 for(register int q = 1;q <= tot;++ q) 69 { 70 int i = cnt[p], j = cnt[q]; 71 if(i == j)continue; 72 //0 0 73 for(register int a = 1;a <= len[i];++ a) 74 { 75 int b = 1, tmp = a; 76 while(s[i][tmp] == s[j][b] && tmp <= len[i] && b <= len[j])++ tmp, ++ b; 77 if(tmp > len[i]) 78 { 79 die[p][0][q][0] = len[i] - a + 1; 80 break; 81 } 82 } 83 //0 1 84 for(register int a = 1;a <= len[i];++ a) 85 { 86 int b = len[j], tmp = a; 87 while(s[i][tmp] == s[j][b] && tmp <= len[i] && b >= 1)++ tmp, -- b; 88 if(tmp > len[i]) 89 { 90 die[p][0][q][1] = len[i] - a + 1; 91 break; 92 } 93 } 94 //1 0 95 for(register int a = len[i];a >= 1;-- a) 96 { 97 int b = 1, tmp = a; 98 while(s[i][tmp] == s[j][b] && tmp >= 1 && b <= len[j])-- tmp, ++ b; 99 if(tmp < 1) 100 {101 die[p][1][q][0] = a;102 break;103 }104 }105 //1 1106 for(register int a = len[i];a >= 1;-- a)107 {108 int b = len[j], tmp = a;109 while(s[i][tmp] == s[j][b] && tmp >= 1 && b >= 1)-- tmp, -- b;110 if(tmp < 1) 111 {112 die[p][1][q][1] = a;113 break;114 }115 }116 }117 ma = 1 << tot;118 }119 120 int main()121 {122 while(scanf("%d", &n) != EOF && n)123 {124 init();125 int flag = 0;126 if(tot == 1)127 {128 int x = cnt[tot];129 for(register int i = 1;i <= len[x];++ i)130 {131 for(register int j = 1;j <= len[x];++ j)132 {133 if(j + i - 1 > len[x]) break;134 int p1 = 1, p2 = j, rank = 0;135 while(s[x][p1] == s[x][p2] && rank < len[x])136 {137 ++ p1, ++ p2, ++ rank;138 if(p1 > len[x]) p1 = 1;139 if(p2 > j + i - 1) p2 = 1;140 }141 if(rank >= len[x])142 {143 printf("%d\n", max(2, i));144 flag = 1;145 break;146 }147 }148 if(flag) break;149 }150 if(flag) continue;151 }152 //dp[S][i][0/1]表示以1号字符串为头，已经选了S，最后一个是i的正/反状态的最大折叠数 153 //dp[S | k][k][p] = max(dp[S | k][k][p], dp[S][i][p'] + die[i][p'][k][p])154 for(register int S = 0;S < ma;++ S)155 for(register int i = 1;i <= tot;++ i)/*分别用dp[S][i][0]和dp[S][i][1]去更新*/156 {157 if(!(S & 1))continue;158 if(!(S & (1 << (i - 1)))) continue;159 for(register int k = 1;k <= tot;++ k)160 {161 if(S & (1 << (k - 1))) continue;162 if(S == 1)163 {164 dp[S | (1 << (k - 1))][k][0] = max(dp[S | (1 << (k - 1))][k][0], dp[S][i][0] + die[i][0][k][0]);165 dp[S | (1 << (k - 1))][k][1] = max(dp[S | (1 << (k - 1))][k][1], dp[S][i][0] + die[i][0][k][1]); 166 }167 else168 {169 dp[S | (1 << (k - 1))][k][0] = max(dp[S | (1 << (k - 1))][k][0], max(dp[S][i][0] + die[i][0][k][0], dp[S][i][1] + die[i][1][k][0]));170 dp[S | (1 << (k - 1))][k][1] = max(dp[S | (1 << (k - 1))][k][1], max(dp[S][i][0] + die[i][0][k][1], dp[S][i][1] + die[i][1][k][1]));171 }172 }173 }174 int ans = 0;175 for(register int i = 1;i <= tot;++i)176 ans = max(ans, max(dp[ma - 1][i][0] + die[i][0][1][0], dp[ma - 1][i][1] + die[i][1][1][0]));177 printf("%d\n", max(2, sum - ans));178 }179 return 0;180 }