UVa1024 Fun Game

我有话说：
此题的要求是，小孩们围成环状，依次报数，男孩为B女孩为G，得到一连串字符串，求其中最小的孩子个数。
首先，我们先不要去想环状，先简化成只是一条直链形的长字符串。既然要求最小，那么我们就要考虑字符串之间的重叠。这样就可以减少字符串的长度。这样的话，我们可以先预处理掉一些被其他字符串完全包含的字符串。因为这样的串完全起不到作用。同样要预处理的是各个串之间的重叠长度。注意到其方向未定，也就是说有可能我们得到的每一个字符串都有可能和实际顺序相反。所以也要枚举它的反串。
这样状态转移方程基本上就可以出来了
d[s][i][x]=min(d[s][i][x],d[s][j][y]);
d[s][j][y]=d[s][i][x]+len[j]-overlap[i][j][x][y];
d[s][i][x]即选用的字符串集合为s，最后结尾的字符串的编号为（i，x）；
x为0表示顺序为1表示逆序，串i的长度为len[i].
最后的时候我们就处理下d[full][i][x]-overlap[i][0][x][0]，如果没能重合那么overlap[i][0][x][0]为0，并没有什么影响。或者有可能是在中间的某一个overlap[i][j][x][y]为0那就直接接上去就行了。
还有一种可能就是这个串重复了好几次得到的，那也没有关系。因为最终就会剩下这么一个字符串。然后在
REP(i,n)REP(j,n)REP(x,2)REP(y,2)
overlap[i][j][x][y]=calc_overlap(s[i][x],s[j][y]);
就只有自己和一部分的自己重叠，因为for(int i=1;i

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
using namespace std;

#define REP(i,n)for(int i=0;i<(n);i++)

const int maxn=16;
const int maxlen=100+10;

int calc_overlap(const string& a ,const string& b)//计算重复部分的串的长度
{
   int lena=a.length(),lenb=b.length();
   for(int i=1;i<lena;i++)
   {
       bool flag=true;
       if(i+lenb<=lena)continue;//string b完全被包含，但这不可能，我们已经删除了所有完全重复子串
       for(int j=0;i+j<lena;j++)
       {
           if(a[i+j]!=b[j]){
              flag=false;
              break;
           }
       }
       if(flag) return lena-i;
   }
   return 0;
}
struct Item{
   string s,rev;
   bool operator < (const Item& rhs)const{
       return s.length()<rhs.s.length();
   }
};
int n;
string s[maxn][2];
int len[maxn];
int overlap[maxn][maxn][2][2];//overlap[i][j][x][y]储存string s[i][x]和s[j][y]最大重叠长度

void Init()
{
   Item tmp[maxn];
   REP(i,n)
   {
       cin>>tmp[i].s;
       tmp[i].rev=tmp[i].s;//wrong
       reverse(tmp[i].rev.begin(),tmp[i].rev.end());
   }
   sort(tmp,tmp+n);
   int n2=0;
   REP(i,n)
   {
       bool need=true;
       for(int j=i+1;j<n;j++)
       {
          if(tmp[j].s.find(tmp[i].s)!=string::npos||tmp[j].rev.find(tmp[i].s)!=string::npos)
          {
              need=false;
              break;
          }
       }
       if(need)
       {
           s[n2][0]=tmp[i].s;
           s[n2][1]=tmp[i].rev;
           len[n2++]=tmp[i].s.length();
       }
   }
   n=n2;
   REP(i,n)REP(j,n)REP(x,2)REP(y,2)
   overlap[i][j][x][y]=calc_overlap(s[i][x],s[j][y]);

}
int d[1<<maxn][maxn][2];//状态定义：d[i][j][x]其中i为二进制所枚举的子集，表示所选用字符串的编号，最后的串是s[j][x]

inline void up_date(int& u,int v)
{
    if(u<0||u>v)u=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(!(i&(1<<j)))//选用的string集合中不包括j号
                    REP(y,2)up_date(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;
        up_date(ans,d[full][i][x]-overlap[i][0][x][0]);
    }
    if(ans<=1)printf("2\n");
    else printf("%d\n",ans);

}

int main()
{
    while(cin>>n&&n)
    {
        Init();
        solve();
    }
    return 0;
}