Pagini recente » Cod sursa (job #1749072) | Cod sursa (job #2110135) | Cod sursa (job #351784) | Istoria paginii runda/pregatire_cls10_oji/clasament | Cod sursa (job #855985)
Cod sursa(job #855985)
#include <fstream>
#include <cstring>
#define NM 20
#define LM 30001
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("adn.in");
ofstream g("adn.out");
int N;
int i,j,k;
int a,b;
int NrPos, ANSPos;
int Size[NM];
char Sir[NM][LM];
int Cost[NM][NM];
int DP[(1 << 18)+23][NM];
int T[(1 << 18)+23][NM];
int PI[NM][LM];
bool Included[NM];
void DoPrefix (int k)
{
int i,j;
for (i=2, j=0, PI[k][1]=0; i<=Size[k]; i++)
{
while (j!=0 && Sir[k][j+1]!=Sir[k][i])
j=PI[k][j];
if (Sir[k][j+1]==Sir[k][i])
j++;
PI[k][i]=j;
}
}
int GetIntersection (int i, int j)
{
int k,q;
for (k=1, q=0; k<=Size[i]; k++)
{
while (q!=0 && Sir[j][q+1]!=Sir[i][k])
q=PI[j][q];
if (Sir[j][q+1]==Sir[i][k])
q++;
if (q==Size[j]) return q;
}
return q;
}
void Print (int Conf, int P)
{
if (Conf==(1 << (P-1)))
{
g << Sir[P]+1;
return;
}
int NConf=Conf^(1 << (P-1));
Print(NConf, T[Conf][P]);
g << Sir[P]+1-Cost[T[Conf][P]][P];
}
int main ()
{
f >> N;
for (i=1; i<=N; i++)
{
f >> (Sir[i]+1);
Size[i]=strlen(Sir[i]+1);
DoPrefix(i);
}
for (i=1; i<=N; i++)
for (j=i+1; j<=N; j++)
{
a=GetIntersection(i, j);
b=GetIntersection(j, i);
if (a==Size[j])
Included[j]=1;
if (b==Size[i] && a!=Size[j])
Included[i]=1;
Cost[i][j]=-a;
Cost[j][i]=-b;
}
memset(DP, INF, sizeof(DP));
for (i=1; i<=N; i++)
if (!Included[i])
{
DP[1 << (i-1)][i]=0;
ANSPos|=(1 << (i-1));
}
NrPos=(1 << N);
for (i=1; i<NrPos; i++)
for (j=1; j<=N; j++)
if (!Included[j] && (i&(1 << (j-1)))!=0 && DP[i][j]!=INF)
for (k=1; k<=N; k++)
if (!Included[k] && ((1 << (k-1))&i)==0 && DP[i^(1 << (k-1))][k]>DP[i][j]+Cost[j][k])
{
DP[i^(1 << (k-1))][k]=DP[i][j]+Cost[j][k];
T[i^(1 << (k-1))][k]=j;
}
for (i=1, j=1; i<=N; i++)
if (DP[ANSPos][i]<DP[ANSPos][j])
j=i;
Print(ANSPos, j);
g << '\n';
f.close();
g.close();
return 0;
}