Mai intai trebuie sa te autentifici.
Cod sursa(job #1588071)
Utilizator | Data | 2 februarie 2016 19:31:47 | |
---|---|---|---|
Problema | ADN | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 4.16 kb |
#include <stdio.h>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#define lmax 30010
using namespace std;
int n,st,nr;
int dp[20][lmax*10],path[20][lmax*10];
int urm[lmax],dif[20][20],sol[20];
bool del[20],viz[20][lmax*10];
string s[20];
char ss[lmax];
vector < pair<int,int> > g[20];
int memo(int nod,int mask)
{
if (viz[nod][mask]) return dp[nod][mask];
viz[nod][mask]=true;
for (unsigned int i=0;i<g[nod].size();i++) {
int y=g[nod][i].first;
if (((mask>>(y-1))&1)==1) {
if (y==st && mask-(1<<(nod-1))!=1<<(y-1)) continue;
int val=memo(y,mask-(1<<(nod-1)))+g[nod][i].second;
if (val>dp[nod][mask]) {
dp[nod][mask]=val; path[nod][mask]=y;
}
}
}
return dp[nod][mask];
}
int nrbit(int x) { return (x&(x-1)); }
void findpath(int nod,int mask)
{
if (mask==(1<<(st-1))) return; else
{
int x=path[nod][mask];
nr++; sol[nr]=nod;
findpath(x,mask-(1<<(nod-1)));
}
}
int main()
{
freopen("adn.in","r",stdin);
freopen("adn.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) {
scanf("%s",ss); s[i]=ss; s[i].insert(0," ");
}
for (int i=1;i<=n;i++)
if (!del[i]) {
for (int j=1;j<=n;j++)
if (i!=j && !del[j]) {
urm[1]=0; int k=0;
for (int l=2;l<(int)s[i].size();l++) {
while (k>0 && s[i][l]!=s[i][k+1]) k=urm[k];
if (s[i][l]==s[i][k+1]) k++;
urm[l]=k;
}
bool ok=false; k=0;
for (int l=1;l<(int)s[j].size();l++) {
while (k>0 && s[j][l]!=s[i][k+1]) k=urm[k];
if (s[j][l]==s[i][k+1]) k++;
if (k==s[i].size()-1) { ok=true; break; }
}
if (ok) { del[i]=true; break; }
}
}
int m=0;
for (int i=1;i<=n;i++)
if (!del[i]) { m++; s[m]=s[i]; }
n=m;
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++)
if (i!=j) {
/*verific daca sufixul lui s[i] se regaseste ca prefix in s[j]; */
urm[1]=0; int k=0;
for (int l=2;l<(int)s[j].size();l++) {
while (k>0 && s[j][l]!=s[j][k+1]) k=urm[k];
if (s[j][l]==s[j][k+1]) k++;
urm[l]=k;
}
k=0;
for (int l=1;l<(int)s[i].size();l++) {
while (k>0 && s[i][l]!=s[j][k+1]) k=urm[k];
if (s[i][l]==s[j][k+1]) k++;
if (k==s[j].size()-1) k=urm[k];
}
g[j].push_back(make_pair(i,k)); dif[j][i]=k;
}
}
for (int i=1;i<=n;i++) s[i].erase(s[i].begin());
int maxx=(1<<n)-1,best=-1,ind=0;
for (int l=1;l<=2;l++) {
st=l;
for (int i=1;i<=n;i++)
for (int j=1;j<=maxx;j++)
dp[i][j]=-1,viz[i][j]=false;
dp[st][1<<(st-1)]=0; viz[st][1<<(st-1)]=true;
for (int j=0;j<(int)g[st].size();j++) {
int val=memo(g[st][j].first,maxx);
if (val>dp[st][maxx]) {
dp[st][maxx]=val; path[st][maxx]=g[st][j].first;
}
}
if (dp[st][maxx]>best) {
ind=l; best=dp[st][maxx];
}
}
if (n==1) dp[1][maxx]=0; st=ind;
for (int i=1;i<=n;i++)
for (int j=1;j<=maxx;j++)
dp[i][j]=-1,viz[i][j]=false;
dp[st][1<<(st-1)]=0; viz[st][1<<(st-1)]=true;
for (int j=0;j<(int)g[st].size();j++) {
int val=memo(g[st][j].first,maxx);
if (val>dp[st][maxx]) {
dp[st][maxx]=val; path[st][maxx]=g[st][j].first;
}
}
findpath(path[ind][maxx],maxx);
nr++; sol[nr]=ind;
reverse(sol+1,sol+nr+1);
for (int i=1;i<nr;i++) {
int y=dif[sol[i+1]][sol[i]];
for (int j=0;j<s[sol[i]].size()-y;j++) printf("%c",s[sol[i]][j]);
}
cout<<s[sol[nr]];
return 0;
}