Cod sursa(job #327513)

Utilizator ConsstantinTabacu Raul Consstantin Data 29 iunie 2009 11:49:05
Problema ADN Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#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,k=0;
for(i=0;i<n;i++)
	if(a[i]==b[k])k++;
	else
	k=0;
return k;
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;}