题意：
给N个字符串，要求出一个序列，在该序列中，后一个串，是由前一个串加一个字母后得来的（顺序可以改动）。
问最多能组成多长的序列。
思路：将给的字符串排序，再对所有的字符串按长度从小到大排序，若长度相同，则按字典序排。
然后找出符合条件的字符串A和B（即B可由A加一个字母得来），建立边的关系。
之后对所有根节点进行dfs深搜，如果当前的长度大于目前的maxlen，则更新，同时记录前驱节点。
最后根据前驱节点，输出路径即可。
#include <stdio.h> #include <map> #include <string.h> #include <algorithm> #include <string> #include <queue> #include <vector> #include <iostream> using namespace std; const int maxn=10005; int n=0; vector<int>son[maxn]; int fa[maxn]; //如果该节点有父节点，则fa[i]=1；否则为0，表示根节点 int tmp[maxn]; //dfs时的前驱 int pre[maxn]; //最大长度序列的前驱,也可以设置后驱，这样会方便点。 int ans[30]; //输出的结果 int maxlen=0; //序列的最大长度 int rear; //最长序列的尾节点 struct Word{ char str1[25],str2[25]; //str1为字符串，str2为对字符串中的字符排好序后的字符串 int len; bool operator<(const Word tmp)const{ if(len==tmp.len){ if(strcmp(str2,tmp.str2)<=0) return true; else return false; } else return len<tmp.len; } }word[maxn]; //判断字符串i和字符串j是否满足条件 bool isOk(int i,int j){ int l1=word[i].len; int l2=word[j].len; int idx=0; while(idx<l1&&word[i].str2[idx]==word[j].str2[idx]) idx++; while(++idx<l2) if(word[i].str2[idx-1]!=word[j].str2[idx]) return false; return true; } //深搜，确定以u为根节点到叶子节点的长度 void dfs(int u,int l){ if(son[u].empty()){ if(l>maxlen){ maxlen=l; int k=u; rear=u; while(tmp[k]!=-1){ pre[k]=tmp[k]; k=tmp[k]; } pre[k]=-1; return; } } int v; for(int i=0;i<son[u].size();i++){ v=son[u][i]; tmp[v]=u; dfs(v,l+1); } } int main() { char s[25]; while(scanf("%s",s)!=EOF){ strcpy(word[++n].str1,s); strcpy(word[n].str2,s); word[n].len=strlen(s); sort(word[n].str2,word[n].str2+word[n].len); } sort(word+1,word+n+1); memset(fa,0,sizeof(fa)); for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(word[i].len+1==word[j].len){ if(isOk(i,j)){ son[i].push_back(j); fa[j]=1; } } //剪枝一下，从1766ms降到1266ms else if(word[i].len+1<word[j].len) break; } } memset(pre,-1,sizeof(pre)); for(int i=1;i<=n;i++){ //加上一个剪枝条件，不过速度没怎么变化。。。 if(!fa[i] && n-i+1>maxlen){ memset(tmp,-1,sizeof(tmp)); dfs(i,1); } } int p=rear; int idx=0; ans[idx++]=p; p=pre[p]; while(p!=-1){ ans[idx++]=p; p=pre[p]; } for(int i=idx-1;i>=0;i--){ printf("%s\n",word[ans[i]].str1); } return 0; }