1699 Best Sequence

問題概要

与えられた文字列全てを(連続する)部分文字列として含むような文字列の最短の長さを求めよ。


文字列の数は10以下、各文字列の長さは20以下である。

解法

この問題は次のような巡回セールスマン問題(ぽいもの)に帰着できる。


文字列Aの接尾辞と文字列Bの接頭辞の共通部分の長さをlとするとき、
AからBに重さstrlen(B)-lの辺を張る。
ある点から出発して、他の全ての点を通る最短距離が求める長さである。


最初の点に戻るか戻らないかで巡回セールスマンとは異なるが、同じビットDPの解法が使える。
(dp[i][j]にiが未訪問のビット、jが現在位置の最適解を入れて更新していく)

ソースコード

int n,m,e[10][10],l[10];
char in[10][21];
int d[1<<10][10];

int solve(int s)
{
	rep(i,1<<n)rep(j,n)d[i][j]=inf;
	d[((1<<n)-1)^1<<s][s]=l[s];
	for(int i=(1<<n)-1;i>=0;i--)rep(j,n)if(d[i][j]!=inf)rep(k,n)if(i&1<<k)
	d[i^1<<k][k]=min(d[i^1<<k][k],d[i][j]+e[j][k]);
	
	int ret=inf; rep(i,n)ret=min(ret,d[0][i]);
	return ret;
}
int main()
{
	scanf("%d",&m);
	rep(i,m)
	{
		scanf("%d",&n);
		rep(j,n)scanf("%s",in[j]),l[j]=strlen(in[j]);
		rep(j,n)rep(k,n)
		{
			int h=min(l[j],l[k]);
			for(;h>0;h--)
			{
				bool ok=1;
				rep(g,h)if(in[j][l[j]-h+g]!=in[k][g])ok=0;
				if(ok)break;
			}
			e[j][k]=l[k]-h;
		}
		
		int ans=inf;
		rep(j,n)ans=min(ans,solve(j));
		printf("%d\n",ans);
	}
	return 0;
}