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;
}

• spj就是答案可能不唯一，符合要求就行，还有，这题有CaseTimeLimit,2000ms,你第一个点就超时了 (2234) TN 2005-05-16 20:15:13