> Source
> 
> Problem Id:2004  User Id:IceAngel 
> Memory:472K  Time:2015MS
> Language:C++  Result:Time Limit Exceed
> 
> Source 
> 
> #include "iostream.h"
> #include "string.h"
> 
> #define wordMax 21
> #define lineMax 10000
> 
> char graph[lineMax][wordMax];
> long map[wordMax][lineMax] = { 0 };
> long num[wordMax] = { 0 };
> long caseLen[wordMax][lineMax] = { 0 };
> long caseMap[wordMax][lineMax] = { 0 };
> long wordsNum;
> long caseNum;
> 
> bool canBeChoose( long pre , long curr )
> {
> 	int preL = strlen( graph[pre] );
> 	int currL = strlen( graph[curr] );
> 
> 	char str[wordMax];
> 	strcpy( str , graph[curr] );
> 	//如果 curr 与 pre 的长度之差不是1，显示不能构成链
> 	if( currL - preL != 1 )
> 		return false;
> 
> 	int i , j;
> 	bool f;
> 	for( i = 0 ; i < preL ; i++ )
> 	{
> 		//判断 pre 中的第i个字符是否在 curr 中出现
> 		f = false;
> 		for( j = 0 ; j < currL && !f ; j++ )
> 			if( graph[pre][i] == str[j] )
> 			{
> 				str[j] = 0;
> 				f = true;
> 			}
> 		if( !f )
> 			return false;
> 	}
> 	return true;
> }
> 
> int main()
> {
> 	char str[wordMax];
> 	long len;
> 	long i , j , k;
> 	
> 	wordsNum = 0;
> 	while( cin >> str )
> 	{
> 		strcpy( graph[wordsNum] , str );
> 
> 		len = strlen( str );
> 		map[len-1][num[len-1]] = wordsNum;
> 		num[len-1]++;
> 
> 		wordsNum++;
> 	}
> 	for( i = 1 ; i < wordMax ; i++ )
> 	{
> 		for( j = 0 ; j < num[i] ; j++ )
> 		{
> 			for( k = 0 ; k < num[i-1] ; k++ )
> 			{
> 				//cout<<graph[map[i-1][k]]<<"\t"<<graph[map[i][j]]<<endl;
> 				if( canBeChoose( map[i-1][k] , map[i][j] ) && caseLen[i-1][k] >= caseLen[i][j] )
> 				{
> 					caseLen[i][j] = caseLen[i-1][k] + 1;
> 					caseMap[i][j] = k;
> 				}
> 			}
> 		}
> 	}
> 
> 	long myMaxLen = 0;
> 	long myX;
> 	long myY;
> 
> 	for( i = wordMax - 1 ; i >= 0 ; i-- )
> 	{
> 		for( j = 0 ; j < num[i] ; j++ )
> 			if( caseLen[i][j] > myMaxLen )
> 			{
> 				myMaxLen = caseLen[i][j];
> 				myX = i;
> 				myY = j;
> 			}
> 	}
> 	for( i = myMaxLen ; i >= 0 ; i-- )
> 	{
> 		num[i] = map[myX][myY];
> 		myY = caseMap[myX][myY];
> 		myX--;
> 	}
> 	for( i = 0 ;i <= myMaxLen ; i++ )
> 	{
> 		cout<<graph[num[i]]<<endl;
> 	}
> 	return 0;
> }
>