Pagini recente » Cod sursa (job #154920) | Monitorul de evaluare | Istoria paginii runda/pie2/clasament | Diferente pentru olimpici intre reviziile 66 si 65 | Cod sursa (job #1532893)
#include<cstdio>
#include<cstring>
#include<vector>
#define inf 2000000000
using namespace std;
char s[20][30010];
int out[20],cost[20][20],prefix[20][30010],norm[20],rev[20],dp[300000][20],dad[300000][20],v[20],len[20];
vector<pair<int,int> > g[20];
void build_prefix(int index){
int n=strlen(s[index]+1),i=0,j;
prefix[index][1]=0;
for(j=2;j<=n;j++){
while(i>0&&s[index][i+1]!=s[index][j])
i=prefix[index][i];
if(s[index][i+1]==s[index][j])
i++;
prefix[index][j]=i;
}
}
void kmp(int first,int second){
int n=strlen(s[second]+1),m=strlen(s[first]+1),i=0,j,ok=1;
for(j=1;j<=n&&ok==1;j++){
while(i>0&&s[first][i+1]!=s[second][j])
i=prefix[first][i];
if(s[first][i+1]==s[second][j])
i++;
if(i==m){
ok=0;
cost[second][first]=0;
out[first]=1;
}
}
if(ok==1)
cost[second][first]=m-i;
}
int main(){
freopen("adn.in","r",stdin);
freopen("adn.out","w",stdout);
int n,i,j,k,nr=-1,dim,curr,answer=inf,config,temp;
scanf("%d\n",&n);
for(i=0;i<n;i++){
scanf("%s",s[i]+1);
len[i]=strlen(s[i]+1);
build_prefix(i);
}
for(i=0;i<n;i++)
for(j=0;j<n;j++){
if(i==j)
continue;
kmp(i,j);
}
for(i=0;i<n;i++)
if(out[i]==0){
nr++;
norm[i]=nr;
rev[nr]=i;
}
for(i=0;i<n;i++)
for(j=0;j<n;j++){
if(i==j||out[i]==1||out[j]==1)
continue;
g[norm[j]].push_back(make_pair(norm[i],cost[i][j]));
}
nr++;
for(i=0;i<(1<<nr);i++)
for(j=0;j<nr;j++){
dp[i][j]=inf;
dad[i][j]=-1;
}
for(i=0;i<nr;i++){
dp[1<<i][i]=strlen(s[rev[i]]+1);
dad[1<<i][i]=-1;
}
for(i=0;i<(1<<nr);i++)
for(j=0;j<nr;j++){
if((i&(1<<j))==0||dp[i][j]!=inf)
continue;
dim=g[j].size();
for(k=0;k<dim;k++){
if((i&(1<<g[j][k].first))==0)
continue;
if(dp[i][j]>dp[i-(1<<j)][g[j][k].first]+g[j][k].second){
dp[i][j]=dp[i-(1<<j)][g[j][k].first]+g[j][k].second;
dad[i][j]=g[j][k].first;
}
}
}
for(i=0;i<nr;i++)
if(dp[(1<<nr)-1][i]<answer){
answer=dp[(1<<nr)-1][i];
curr=i;
}
k=0;
config=(1<<nr)-1;
i=curr;
while(i!=-1){
k++;
v[k]=rev[i];
temp=i;
i=dad[config][i];
config=config-(1<<temp);
}
printf("%s",s[v[nr]]+1);
for(i=nr-1;i>=1;i--)
for(j=cost[v[i+1]][v[i]];j>0;j--)
printf("%c",s[v[i]][len[v[i]]-j+1]);
return 0;
}