boj 377

Description
相信大家都玩过成语接龙吧，现在我们来玩一个单词接龙的游戏。游戏是在一个单词表上进行的，我们定义单词B可以接在单词A后，当且仅当A是B的前缀且B不等于A。考察如下的单词表：i、in、ix、int，一共有i->in、i->ix、i->int、in->int共4种接法。
现在给定一个单词表，求出这个单词表可以构成的最长单词串包含的单词个数。


Input
输入包含多组测试数据。
首先第一行输入一个数T(T<=50)，表示总共有T组测试数据。
接下来是每组测试数据，第一行是一个数N(1<=N<=200)，表示该单词表有N个单词。然后接下来的N行，每行一个单词(每个单词的长度<=200)。


Output
首先，输出Case #X：其中X代表是第X组数据(具体格式参照样例)。
对于每组测试数据，输出最长的单词串包含的单词个数。


Sample Input

1
5
i
in
ix
int
inty


Sample Output

Case #1:
4

 

水题，原理和最大递增子序列一样，dp[i]表示最后一个单词为a[i]的最长单词串

代码：

 

#include<iostream>
#include<string>
using namespace std;

#define N 205

char a[N][N];
int dp[N];
int main()
{
	int t,cnt=1;
	scanf("%d\n",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%s",a[i]);
		int max=1;
		for(int i=1;i<=n;i++)
		{
			dp[i]=1;
			int len1=strlen(a[i]);
				for(int j=1;j<i;j++)
				{
					int len2=strlen(a[j]);
					char b[N];
					if(len1>len2)
					{
					memcpy(b,&a[i][0],len2*sizeof(char));
					b[len2]=0;
					if(strcmp(a[j],b)==0&&dp[i]<dp[j]+1)
						dp[i]=dp[j]+1;
					}
				}
				max<dp[i]?max=dp[i]:max;
		}
		printf("Case #%d:\n%d\n",cnt++,max);
	}
}