1709.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"memory.h"
#include"string.h"
char word[1000][23];
int index[27];
int n,l,len[1000],set[1000];
void init()
{
	int i;
	for(i=0;i<26;i++)index[i]=n;

	for(i=0;i<n;i++)
	{
		cin>>word[i];
		len[i]=strlen(word[i]);
		if(index[word[i][0]-'a']==n)index[word[i][0]-'a']=i;
	}

	memset(set,1,1000*sizeof(int));
}

char best[100];int go;
char w[100];


void find(int a,int b)
{
	if(go&&strcmp(w,best)>0)return;

	if(b==a&&a)
	{
		if(a==l&&!go)
		{
			strcpy(best,w);go=1;
		}

		else if(a==l&&strcmp(w,best)<0)
			strcpy(best,w);
		return;
	}

	if(a>=l||b>l)return;
	int i,j;
	for(i=(a==0?0:index[w[a]-'a']);i<n&&(a==0||word[i][0]==w[a]);i++)
	if(set[i])
	{
		for(j=a;j<b&&j-a<len[i];j++)
		{
			if(word[i][j-a]!=w[j])break;
		}
		if(j>=b)
		{
			w[a]=0;
			strcat(w,word[i]);
			set[i]=0;				
			if(go&&strcmp(w,best)>0)
			{
				w[b+1]=0;set[i]=1;return;
			}
		
			find(b,a+len[i]);		
			w[b+1]=0;
			set[i]=1;

		}
		if(j-a>=len[i])
		{
			set[i]=0;	
			find(a+len[i],b);
			set[i]=1;
		}
	}
return;

}
int main()
{
	cin>>l>>n;
	init();
	w[0]=0;go=0;
	find(0,0);
	if(n>1&&go)cout<<best<<endl;
	else cout<<"NO SOLUTION"<<endl;
	return 0;
}