记录编号	481519	评测结果	WWWWWWWWWW
题目名称	726.[SDOI 2007] 单词接龙游戏	最终得分	0
用户昵称	PSI	是否通过	未通过
代码语言	C++	运行时间	2.071 s
提交时间	2018-01-03 11:12:36	内存使用	2.53 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int i,j,a,b,c,d,k,ans,f[10005],qj[10005],n,o;
struct ci
{
    char str[105];
	int cs[28],l;
}dc[10005];
bool cmp(ci a,ci b)
{
	return a.l<b.l;
}


int main()
{
	freopen("wordgame.in","r",stdin);
	freopen("wordgame.out","w",stdout);	
	while(scanf("%s",dc[n+1].str)!=EOF)
	{
		++n;
		int l=strlen(dc[n].str);
		dc[n].l=l;
		for(i=0;i<l;i++)
		dc[n].cs[dc[n].str[i]-'a']++;		
	}
	sort(dc+1,dc+1+n,cmp);
	for(i=1;i<=n;i++)
	{f[i]=1;
	 qj[i]=0;
	for(j=i-1;j>=1;j--)
	{   if(dc[j].l<dc[i].l-1)break;
		if(f[j]<f[i]||dc[j].l==dc[i].l)continue;
     	bool	ky=1;
		int k;
		for(k=0;k<=25;k++)
		{
		if(dc[i].cs[k]<dc[j].cs[k]){ky=0;break;}
		}		
		if(ky==0)continue;
		f[i]=f[j]+1;
		qj[i]=j;	
	}
	if(f[i]>ans)
	ans=f[i],o=i;
}
int lin[10005];lin[0]=0;
printf("%d\n",ans);
	for(;o!=0;o=qj[o])
	{
		lin[++lin[0]]=o;	
	}
	for(i=lin[0];i>=1;i--)
	{
		printf("%s\n",dc[lin[i]].str);
	}
	
	
}