当前位置: 代码迷 >> 综合 >> poj 1699 Best Sequence 枚举排列
  详细解决方案

poj 1699 Best Sequence 枚举排列

热度:98   发布时间:2024-01-19 06:30:41.0

题意:

给n个字符串,求合并后字符串的最小长度,合并的规则是合并后对应位字符一样,比如abc和bcd可以合并为abcd.

思路:

本来想dp的,但一看n<=10,一脸欠搜的样,于是枚举各串在最终串中的顺序,选最小长度。要注意的是任意两串合并的新串长度要预处理,否则在枚举过程中计算会超时。

代码:

//poj 1699
//sepNINE
#include <iostream>
#include <algorithm>using namespace std;
char seg[16][32];
char tmp[16];
int cnt[16][16];
int lens[16];
int a[16];
int p;
int add(int x,int y){int p=strlen(seg[x]);int i,j,len=strlen(seg[y]);for(i=0;i<p;++i)tmp[i]=seg[x][i];for(i=p-len;i<=p;++i){int flag=1;if(i<0) continue;for(j=0;j<len&&i+j<p;++j)if(tmp[i+j]!=seg[y][j]){flag=0;break;}if(flag==1)return j;}
}int main()
{int cases;scanf("%d",&cases);while(cases--){int n,i,j,ans;scanf("%d",&n);ans=n*20;for(i=1;i<=n;++i)scanf("%s",seg[i]);for(i=1;i<=n;++i)for(j=1;j<=n;++j)cnt[i][j]=add(i,j);for(i=1;i<=n;++i){lens[i]=strlen(seg[i]);a[i]=i;}do{p=lens[a[1]];for(i=2;i<=n;++i){p=p+lens[a[i]]-cnt[a[i-1]][a[i]];	if(p>=ans)break;}ans=min(ans,p);}while(next_permutation(a+1,a+n+1));printf("%d\n",ans);}return 0;	
} 


  相关解决方案