poj_1699.txt

poj 1699的代码和方法说明,个人原创

#include<iostream>
#include<string>
using namespace std;
int statedp[11][1025],n,len[11];
char ch[11][21];
int com[11][11];//表示当i字符串和j字符串连接时,组合串的最小长度
int searchs(int a,int state,int total)//a表示以哪个字符串为首串,state表示要连接的串有哪些
                          //这是一个二进制表示,例如state=001101表示要连接的串为第1个第三个,第4个
        //total表示state中二进制位1的个数
        //state[1][0011]表示当把第1个和第2个连接时,第1个放在第一位,可以获得的最小串;
{
if(statedp[a][state]!=-1)
   return statedp[a][state];
if(total==1)
{
   return statedp[a][state]=len[a];
}
int s=state&(~(1<<(a-1)));//把a所在的二进制位置0;
int p=total-1;
int i,j,k,temp;
for(i=0;p;i++)
{
   k=1<<i;
   if(j=(s&k))
   { p--;
    temp=searchs(i+1,s,total-1)+com[a][i+1]-len[i+1];
    if(statedp[a][state]==-1||temp<statedp[a][state])
     statedp[a][state]=temp;
   }
}
return statedp[a][state];
}



int main()
{
int cas,i,j,k,tt,k1,fe;
scanf("%d",&cas);
while(cas--)
{
   scanf("%d",&n);
   for(i=1;i<=n;i++)
   { scanf("%s",&ch[i][1]);
   len[i]=strlen(&ch[i][1]);
   }
  
   if(n==1)
   { cout<<len[1]<<endl;
   continue;
   }
   memset(com,-1,sizeof(com));
   memset(statedp,-1,sizeof(statedp));
   for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)//计算com[i][j];
    { tt=0;
     for(k=1;k<=len[i];k++)
     {
      if(ch[i][k]==ch[j][1])
      { 
       fe=k+1;
       k1=2;
       while(fe<=len[i]&&ch[i][fe]==ch[j][k1])
       { fe++;
          
        k1++;
       }
       if(fe>len[i])
       { com[i][j]=k-1+len[j];
      k=len[i]+10;
       }
       tt=0;
      }
     }
     if(com[i][j]==-1)
      com[i][j]=len[i]+len[j];
    }
   int ans=100000000,p;
   for(i=1;i<=n;i++)
   {
    p=searchs(i,(1<<n)-1,n);//枚举以每个字符串为首串的最小值;
    if(p<ans)
    ans=p;
   }
   cout<<ans<<endl;
}
return 0;
}