2663 - 魔族密码
时间限制 : 1 秒
内存限制 : 128 MB
风之子刚走进他的考场，就……
风之子：我呕……（杀死人的眼神）快说题目！否则……--###
花花：……咦好冷我们现在要解决的是魔族的密码问题（自我陶醉：搞不好魔族里面还会有人用密码给我和菜虫写情书咧，哦活活，当然是给我的比较多 拉*^^*）。魔族现在使用一种新型的密码系统。每一个密码都是一个给定的仅包含小写字母的英文单词表，每个单词至少包含1个字母，至多75个字母。如 果在一个由一个词或多个词组成的表中，除了最后一个以外，每个单词都被其后的一个单词所包含，即前一个单词是后一个单词的前缀，则称词表为一个词链。例如 下面单词组成了一个词链：
i
int
integer
但下面的单词不组成词链：
integer
intern
现在你要做的就是在一个给定的单词表中取出一些词，组成最长的词链，就是包含单词数最多的词链。将它的单词数统计出来，就得到密码了。
<span style="font-size:12.0pt;font-family:宋体;">风之子：密码就是最长词链所包括的单词数阿<span>……</span></span>
题目输入
第一行为单词表中的单词数N（1<=N<=2000），下面每一行有一个单词，按字典顺序排列，中间也没有重复的单词。
题目输出
一行，即密码（也就是单词的个数）
输入/输出样例
输入格式
5 i int integer intern internet
输出格式
4
C语言解答
#include "stdio.h" int n,max; char a[2000][80]; int b[2000]; int F(int x,int y) { int i,j; int d1,d2; d1=strlen(a[x]); d2=strlen(a[y]); if(d1<=d2) return 0; for(i=0;i<d2;i++) if(a[x][i]!=a[y][i]) return 0; return 1; } int main() { int i,j; scanf("%d",&n); for(i=0;i<n;i++) scanf("%s",a[i]); for(i=1;i<n;i++) { for(j=0;j<i;j++) if(F(i,j)&&b[i]==b[j]) b[i]++; } max=0; for(i=1;i<n;i++) { if(max<b[i]) max=b[i]; } printf("%d\n",max+1); return 0; }
C++解答
#include<iostream> #include<cstring> #include<string> using namespace std; string s[2001]; string s1; int n; int h[2001]={0}; int w[2001]={0}; int m=0; void init(); void work(); int main() { init(); work(); return 0; } void init() { cin>>n; for(int i=1;i<=n;++i) { cin>>s[i]; h[i]=s[i].size(); w[i]=1; } } void work() { for(int i=2;i<=n;++i) { for(int j=1;j<i;++j) { s1=s[i].substr(0,h[j]); if(h[i]>h[j]&&w[j]+1>w[i]&&s1==s[j]) { w[i]=w[j]+1; } } if(w[i]>m) { m=w[i]; } } cout<<m; }