bzoj 1195: [HNOI2006] 최단 모직(상압 dp)

1195: [HNOI2006] 최단 모직
Time Limit: 10 Sec  
Memory Limit: 32 MB
Submit: 1212  
Solved: 405
[ Submit][ Status][ Discuss]
Description
문자열 n개(S1, S2, 으, Sn)를 지정하려면 이 문자열 n개(S1, S2, 으, Sn)가 모두 T의 하위 문자열이 되도록 가장 짧은 문자열 T를 찾아야 한다.
Input
첫 번째 줄은 정해진 문자열의 개수를 나타내는 정수 n(n<=12)이다.다음 n 행에는 모두 대문자로 구성된 문자열이 있습니다.각 문자열의 길이는 50을 초과하지 않습니다.
Output
가장 짧은 문자열 T를 찾으려면 한 줄만 있습니다.가장 짧은 전제에서 여러 문자열이 요구를 충족시키려면 사전 순서에 따라 첫 번째 문자열을 출력해야 한다.
Sample Input
2 ABCD BCDABC
Sample Output
ABCDABC
HINT
Source
[ Submit][ Status][ Discuss]

장압
답안에 문자열 i가 포함되어 있는지 여부를 눌러라.
f[i][j]는 상태 i를 표시하고 맨 앞의 문자열은 j의 최소 연결 방식의 다음 문자열의 번호를 표시합니다
g[i][j]는 상태 i를 나타내고 맨 앞의 문자열은 j의 현재 길이를 나타낸다
h[i][j]기록은 어느 상태에서 밀어온 것입니까?
이동할 때 기록된 후계자에 따라 문자열을 복원하여 대비해야 한다

#include
#include
#include
#include
#include
#include
#define N 15
#define pa pair
using namespace std;
int f[(1<<12)][13],g[(1<<12)][13],h[(1<<12)][13],can[(1<<12)][13];
int n,m,ans,c[N][N];
char a[N][100],b[N][100],str[2000],s[603],s1[603];
int len[N],len1[N],mark[N];
int calc(char a[],char b[],int len,int len1)
{
	int ans=0;
	for (int i=1;i<=len;i++)
	 {
	 	int j=1; int k=i;
	 	while (a[k]==b[j]&&k<=len&&j<=len1) k++,j++;
	 	if (k==len+1)  ans=max(ans,j-1);
	 }
	return ans;
}
bool pd(char x[],char y[],int len)
{
	for (int i=1;i<=len;i++)
	 if (x[i]y[i]) return true;
	return false;
}
int change(int x,int sta,int lenk,int last,char s[])
{
	int t;
	if (last==-1)    t=calc(s,a[x],lenk,len[x]);
	else t=c[last][x];
	for (int i=t+1;i<=len[x];i++)
	 s[++lenk]=a[x][i];
	if (f[sta][x]==0)  return lenk;
	change(f[sta][x],h[sta][x],lenk,x,s);
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%s",b[i]+1);
		len1[i]=strlen(b[i]+1);
	}
	for (int i=1;i<=n;i++)
	 if (!mark[i])
	 for (int j=1;j<=len1[i];j++)
	  {
	  	for (int k=1;k<=n;k++)
	  	 if (k!=i)
	  	  {
	  	  	 bool f=true;
	  	  	 for (int l=1;l<=len1[k];l++)
	  	  	  if (b[i][j+l-1]!=b[k][l]){
	  	  	  	f=false;
	  	  	  	break;
				  }
			 if (f&&j+len1[k]-1<=len1[i])
			  mark[k]=1;
		  }
	  }
	int cnt=0;
	for (int i=1;i<=n;i++)
	 if (!mark[i]) {
	 	cnt++; len[cnt]=len1[i];
	 	for (int j=1;j<=len[cnt];j++)
	 	 a[cnt][j]=b[i][j];
	 }
	n=cnt; 
	for (int i=1;i<=n;i++) c[0][i]=0;
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=n;j++)
	  if (i!=j)  c[i][j]=calc(a[i],a[j],len[i],len[j]);
	memset(f,-1,sizeof(f));
	queue p;
	for (int i=1;i<=n;i++)
	 f[1<>(j-1))&1))
	   	   {
	   	   	 for (int k=1;k<=len[j];k++) s1[k]=a[j][k];
	   	   	 int t=change(i,sta,len[j],-1,s1);
	   	   	 if (f[sta|(1<