3980905_re.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <string>
#include <algorithm>
#define inf 2100000000
using namespace std;

int Min[15][1<<15];

int main()
{
	int cas, n, i, j, k, N, p, now, last;
	string dna[15];
	char tmp[101];
	int over[15][15];
	
	int a[15];

	a[0] = 1;
	for (i = 1; i < 15; i++)
	{
		a[i] = a[i-1]<<1;
	}
	scanf("%d", &cas);
	for (now = 1; now <= cas; now++, puts("\n"))
	{
		printf("Scenario #%d:\n", now);
		scanf("%d", &n);
		for (i = 0; i < n; i++)
		{
			scanf("%s", tmp);
			dna[i] = string(tmp);
		}
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < n; j++)
			{
				if (i != j && dna[j].find(dna[i]) != string::npos)
				{
					dna[i--] = dna[--n];
				}
			}
		}
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < n; j++)
			{
				over[i][j] = dna[i].length();
				while ( dna[i].substr(dna[i].length()-over[i][j]) != dna[j].substr(0, over[i][j]))
				{
					over[i][j]--;
				}
			}
		}
		N = 1 << n;
		for (i = 1; i < N; i++)
		{
			for (j = 0; j < n; j++)
			{
				if (!(i & a[j]))
					continue;
				p = i ^ a[j];
				Min[j][i] = p ? inf : dna[j].length();
				for (k = 0; k < n; k++)
				{
					if (!(p & a[k]))
						continue;
					int tmp = dna[j].length() - over[j][k] + Min[k][p];
					if (tmp < Min[j][i])	Min[j][i] = tmp;
				}
			}
		}
		N--;
		last = -1;
		while(N)
		{
			int best = -1;
			int bestLen;
			string bestAdd;
			 
			for (i = 0; i < n; i++ )
			{
				if (!(N & a[i]))
					continue;
				int len = Min[i][N];
				string add = dna[i];
				if( last != -1)
				{
					len -= over[last][i];
					add = add.substr(over[last][i]);
				}
				if(best == -1 || len < bestLen || (len==bestLen && add<bestAdd))
				{
					best = i;
					bestLen = len;
					bestAdd = add;
				}
			}
			printf("%s", bestAdd.c_str());
			last = best;
			N ^= 1 << best;
		}
	}
	return 0;
}