Pagini recente » Cod sursa (job #3158489) | Cod sursa (job #3276250) | Cod sursa (job #1090722) | Cod sursa (job #2692677) | Cod sursa (job #327504)
Cod sursa(job #327504)
#include<fstream>
#include<string.h>
#include<stdio.h>
using namespace std;
int cost[20][20],sol[20][20],viz[20][20],n,i,min1=50000;
char a[20][30010];
void citire(){
int i;
ifstream f("adn.in");
f>>n;
for(i=1;i<=n;i++)
f>>a[i];
}
void eliminare(){
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(strstr(a[j],a[i])&&i!=j){
{
strcpy(a[i],a[n]);
n--;
}
}
}
int calc_cost(char *a,char *b){
int n=strlen(a);
int i;
for(i=0;i<n;i++)
if(strstr(b,a+i)==b)return n-i;
return 0;
}
void afisare(int v[]){
int i,m,j;
freopen("adn.out","w",stdout);
for(i=1;i<n;i++)
{m=strlen(a[v[i]]);
for(j=1;j<=m-cost[v[i]][v[i+1]];j++)
printf("%c",a[v[i]][j-1]);
}
printf("%s",a[v[n]]);
}
void cost1(){
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
cost[i][j]=calc_cost(a[i],a[j]);
int max1,poz,x,S,max2=0;
for(i=1;i<=n;i++)
{viz[i][i]=1;
x=i;
sol[i][1]=i;
for(j=2;j<=n;j++)
{max1=-1;
for(k=1;k<=n;k++)
if((cost[x][k]>max1))
if((viz[i][k]==0))
{max1=cost[x][k];poz=k;}
sol[i][j]=poz;x=poz;sol[i][19]+=max1;viz[i][poz]=1;}
if(sol[i][19]>max2){max2=sol[i][19];S=i;}
}
afisare(sol[S]);
}
int main(){
citire();
eliminare();
cost1();
return 0;}