学步园

Description

Input

Output

Sample Input

ab
arc
arco
bar
bran
carbon
carbons
cobra
crab
crayon
narc

Sample Output

ab
bar
crab
cobra
carbon
carbons

题意：输出若干字符串中按照如下规则的最长的字符串序列（规则：从短到长，并且相邻的两个字符串只一个字符）。

思路：类似dp的方法，dp[i]=max(dp[i],dp[j]+1),其中j是i加一个字符变成的串...，按照这个思路写的代码 4875MS 险过。。

 #include<iostream>
#include<algorithm>
using namespace std;
char str[10010][30];	int lenth[10010],list[10010][26],next[10010],start,maxl,listl[10010],n;

bool cmp(int i,int j)
{
	int l=-1;
	i=lenth[i]%100000;
	j=lenth[j]%100000;
	for(int k=0;k<26;k++)
		if(list[i][k]!=list[j][k]&&l!=-1)
			return false;
		else if(list[i][k]!=list[j][k])
			l=k;
	if(list[j][l]-list[i][l]==1)
		return true;
}

void find(int i)
{
	int j=i+1;
	for(;j<n;j++)
		if(lenth[j]/100000-lenth[i]/100000==1&&cmp(i,j)&&listl[i]<listl[j]+1)
		{
			listl[i]=listl[j]+1;
			next[i]=j;
		}
	if(listl[i]>maxl)
	{
		maxl=listl[i];
		start=i;
	}
}



int main()
{
	int i;
	memset(list,0,sizeof(int)*10010*26);
	memset(next,0,sizeof(int)*10010);
	memset(listl,0,sizeof(int)*10010);
	n=0;
	while(scanf("%s",str[n])!=EOF)
	{
		for(i=0;str[n][i]!='/0';i++)
			list[n][str[n][i]-97]++;
		lenth[n]=i*100000+n;
		n++;
	}
	sort(lenth,lenth+n);
	maxl=0;
	for(i=n-1;i>-1;i--)
		find(i);
	do
	{
		cout<<str[lenth[start]%100000]<<endl;
		start=next[start];
	}while(start);
}