Cod sursa(job #327542)

Utilizator ConsstantinTabacu Raul Consstantin Data 29 iunie 2009 12:32:30
Problema ADN Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<fstream>
#include<string.h>
#include<stdio.h>
using namespace std;

int cost[20][20],sol[20],viz[20],v[20],max1=-1,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;
}

void afisare(int v[]){
int i;
freopen("adn.out","w",stdout);

for(i=1;i<=n;i++)
	printf("%s",a[v[i]]+cost[v[i-1]][v[i]]);
}

void cost1(){
int i,j;


for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	if(i!=j)
		cost[i][j]=calc_cost(a[i],a[j]);


}


void cond(){
int i,sum=0;

for(i=1;i<n;i++)
	sum+=cost[v[i]][v[i+1]];
if(sum>max1){max1=sum;memcpy(sol,v,sizeof(v));}
}

void back(int lvl){
if(lvl==n)cond();
else
{int i;
for(i=1;i<=n;i++)
	if(!viz[i])
		{viz[i]=1;
		v[lvl+1]=i;
		back(lvl+1);
		viz[i]=0;}

}
}
int main(){
citire();
eliminare();
cost1();
back(0);
afisare(sol);
return 0;}