// UVa 1204
题意：一些小孩（至少是两个）围成一圈做游戏。每一轮从某个小孩开始往他左边或右边传手帕。
一个小孩拿到手帕后（包括第一个小孩）在手帕上写下自己的性别，男孩写B，女孩写G，
然后按相同的方向传给下一个小孩，每一轮可能在任何一个小孩写完后停止。
现在游戏已经进行了n轮，已知n轮中每轮手帕上留下的字，求最少有几个小孩。
每轮手帕上的数字不超过100。
2 <= n <= 16
思路：我们可以将问题进行简化，将圈先转化成一条线，
然后解决线上面的动态规划，然后将它转换成圈。
对于线上的问题，我们要寻找出最短的序列，使之序列包含上述n个子序列，
那么对于k序列我们想要插入上述序列，与k序列有关系的只有k前面的序列（k插入位置的前面那个序列）
所以我们的状态要包含最后一个序列是什么，然后我们的状态需要包含在不同范围（i-j）中的最有解是什么，
然后逐步扩大范围，最后输出全集（1-n）的最有解即可，所以我们的状态一定要包含一个集合，对于2<=n<=16
来说，这个范围刚好（不大不小，可以将集合表示出来），所以可以得到最终的状态的定义：
d(s,j)表示s集合其中j元素为结尾的最短序列。
其次就是状态转移方程:
d(s,j) = min(d(s-{j}, i)+t(j)-both(i,j)) (其中both(i,j)表示以i为头以j为尾的公共部分)
然后采用递推的方法将集合枚举的越来越大，然后求解，一共有(n*2^n)中状态，每个状态有(n)种决策方式，
所以时间复杂度为O(n^2*2^n)
下面来说一说将线(或行)转化成圈的过程吧!
(1)原题说了可以顺时针也可以逆时针，这在上面处理线时并没有考虑，每个状态d(i,j)有2n中可能，决策数也变成2n，
这仅仅是常数的变换，所以时间复杂度并没有改变，在处理时我们要考虑是正过来"粘"还是倒过来"粘"。
(2)其次就是考虑园首尾相连的特征，所以我们在进行，处理园的时候要考虑结尾与开头之间的重叠部分，
所以需要知道这个状态第一个序列的摆放位置，好像不必增加维度就能够处理(那一定是状态定义上的"约束"了)，
然后考虑输入字符串可能是不是圈的一部分，而是绕了很多圈以后的结果，这个会不会影响以及怎么做就需要看代码了，
然后对于如果算出的结果为1的话，我们需要输出2。
后面就是代码实现了，下面可能说代码处理的问题（也可能不）。
补充(代码处理以及忘了说的地方)
1.如何处理首位接应的问题，我想了想，还是增加一位来记录第一个序列是什么，但是不用确定第一个序列的方向（或是说，只需要
一个方向就行，所以代码上我只规定了正方向）（这样不会丢失最优解，想一想，为什么？）。
2.然后就是将之间的东西进行简化，我说一说输入，如果给的两个序列i，j其中i∈j（竟然会了打数学符号，哈哈），那么我们
不需要考虑i，想一想为什么，这样简化问题能够促使我们想出一些思路的。
通过编写带代码，我发现了几个自己并不能够实现的问题，下面说一说问题与lrj的解决思路：
1、如何判断输入的两个序列中其中一个包含另一个？ 使用stl的string中的find函数。
2、为什么可以不需要增加一维来记录开始的部分？ 任选一个序列的正方向作为开头就行。(这样也不会丢失最优解？想一想，为什么？)
3、对于一个序列可能绕了几圈怎么解决？ 这个会在最后末尾"粘贴"到头的时候有所体现（这个我想的也不太清楚）。
下面是代码实现:
// UVa 1204 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <string> using namespace std; #define REP(i,n) for (int i = 0; i < (n); ++i) const int maxn = 16; int calc_overlap(const string& a, const string& b) { int n1 = a.length(); int n2 = b.length(); for (int i = 1; i < n1; ++i) { if (n2+i <= n1) continue; bool ok = true; for (int j = 0; j+i < n1; ++j) if (a[j+i] != b[j]) { ok = false; break; } if (ok) return n1-i; } return 0; } struct Seq { string s, rev; bool operator < (const Seq& rhs) const { return s.length() < rhs.s.length(); } } seq[maxn]; int n; string new_seq[maxn][2]; int len[maxn]; int overlap[maxn][maxn][2][2]; void init() { REP(i, n) { cin >> seq[i].s; seq[i].rev = seq[i].s; reverse(seq[i].rev.begin(), seq[i].rev.end()); } int n2 = 0; sort(seq, seq+n); REP(i, n) { bool need = true; for (int j = i+1; j < n; ++j) { if (seq[j].s.find(seq[i].s) != string::npos || seq[j].rev.find(seq[i].s) != string::npos) { need = false; break; } } if (need) { new_seq[n2][0] = seq[i].s; new_seq[n2][1] = seq[i].rev; len[n2] = seq[i].s.length(); n2++; } } n = n2; REP(i, n) REP(j, n) REP(x, 2) REP(y, 2) overlap[i][j][x][y] = calc_overlap(new_seq[i][x], new_seq[j][y]); } int d[1<<maxn][maxn][2]; void update(int& x, int v) { if (x < 0 || v < x) x = v; } void solve() { memset(d, -1, sizeof(d)); d[1][0][0] = len[0]; int full = (1<<n)-1; for (int s = 1; s < full; ++s) REP(i, n) REP(x, 2) if (d[s][i][x] >= 0) for (int j = 1; j < n; ++j) if (!(s&(1<<j))) REP(y, 2) update(d[s|(1<<j)][j][y], d[s][i][x]+len[j]-overlap[i][j][x][y]); int ans = -1; REP(i, n) REP(x, 2) { if (d[full][i][x] < 0) continue; update(ans, d[full][i][x]-overlap[i][0][x][0]); } if (ans <= 1) ans = 2; printf("%d ", ans); } int main() { while (scanf("%d", &n) == 1 && n) { init(); solve(); } return 0; }