如题

啊啊啊啊啊打炸了疯了啊啊啊啊啊

//SIXIANG
#include <iostream>
#include <algorithm> 
#include <cstring>
#define MAXN 100000
#define QWQ cout << "QWQ" << endl;
using namespace std;
struct node {
	string str, rev;
} Q[16 + 10], P[16 + 10];
bool cmp(node &x, node &y) {
	return x.str.size() < y.str.size();
}
bool del[16 + 10];
int f[20][(1 << 16) + 10][2];
void update(int &x, int y) {
	x = min(x, y);
}
int cost(string a, string b) {//a 在 b 前 
	int len1 = a.size();
	int len2 = b.size();
  	for(int i = 0; i < len1; i++) { // place b at position i
   		if(len2 + i <= len1) continue; // b cannot extend to the right of a
    	bool ok = true;
    	for(int j = 0; i + j < len1; j++)
      		if(a[i+j] != b[j]) {ok = false; break; }
    	if(ok) return len1 - i;
  	}
  	return 0;
}
int ct[20][20][2][2];
int init() {
	memset(del, 0, sizeof(del)); 
	int n; cin >> n;
	if(!n) return -1;
	for(int p = 0; p < n; p++) {
		cin >> Q[p].str;
		Q[p].rev = Q[p].str;
		reverse(Q[p].rev.begin(), Q[p].rev.end());
	}
	sort(Q, Q + n, cmp);
	
	for(int p = 0; p < n; p++)
		for(int i = p + 1; i < n; i++) {
			string s1 = Q[i].str, s2 = Q[p].str, s3 = Q[i].rev;
			if(s1.find(s2) != string::npos
			|| s3.find(s2) != string::npos) {
				del[p] = 1;
				break;
			}
		}
	int t = 0;
	for(int p = 0; p < n; p++)
		if(!del[p])
			P[t++] = Q[p];
	n = t;
	for(int p = 0; p < n; p++)
		Q[p] = P[p];
	
	memset(f, 0x3f, sizeof(f));
	const int inf = f[0][0][0];
	for(int p = 0; p < n; p++)
		f[p][(1 << p)][0] = f[p][(1 << p)][1] = Q[p].str.size();
	f[0][1][1] = inf;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++) {
			ct[i][j][0][0] = cost(Q[i].str, Q[j].str);
			ct[i][j][0][1] = cost(Q[i].str, Q[j].rev);
			ct[i][j][1][0] = cost(Q[i].rev, Q[j].str);
			ct[i][j][1][1] = cost(Q[i].rev, Q[j].rev);
		}
	for(int S = 0; S < (1 << n); S++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				if(i != j && ((S >> j) & 1) == 0 && ((S >> i) & 1) == 1) {
					if(f[i][S][0] != inf) {
						int len = Q[j].str.size(); 
						update(f[j][S + (1 << j)][0], f[i][S][0] + len - ct[i][j][0][0]);
						update(f[j][S + (1 << j)][1], f[i][S][0] + len - ct[i][j][0][1]);
					}
					if(f[i][S][1] != inf) {
						int len = Q[j].str.size();
						update(f[j][S + (1 << j)][0], f[i][S][1] + len - ct[i][j][1][0]);
						update(f[j][S + (1 << j)][1], f[i][S][1] + len - ct[i][j][1][1]);
					}
				}
 
 	int minn = 1145141919;	
	if(n == 1) {
		int len = Q[1].str.size();
		int c1 = cost(Q[1].str, Q[1].str);
		int c2 = cost(Q[1].rev, Q[1].rev);
		int ans = min(len - c1, len - c2);
		cout << max(ans, 2) << endl;
		return 0;
	}
	for(int p = 1; p < n; p++) {//有环，规定 1 是第一个 
		int len = Q[p].str.size();
		minn = min(minn, f[p][(1 << n) - 1][0] - cost(Q[p].str, Q[0].str));
		minn = min(minn, f[p][(1 << n) - 1][1] - cost(Q[p].rev, Q[0].str)); 
	}
	if(minn <= 1) cout << 2 << endl;
	else cout << minn << endl;
	return 114514; 
}
int main() {
//	freopen("read.txt", "r", stdin);
//	freopen("write.txt", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	while(1) if(init() < 0) return 0;
}