P1019 单词接龙

P1019 单词接龙

首先需要找到任意两个单词的最小重合长度：从前面单词的尾部比较，依次增加尾部选取长度，直至找到选取尾部和下一个单词头部相同，就找到了最小重合长度。
再通过dfs搜索。

#include<bits/stdc++.h>
using namespace std;
int n,sum=0;
char str[20][50],ch;//str单词、ch首字母 
int a[20][20]={0};//a[i][j]的值表示i单词接j单词的最小重合长度 
int b[20]={0};//b[i]的值表示i单词使用过的次数 
int c[20]={0};//c[i]的值表示i单词的长度 
int max1=0;
void dfs(int i){
	bool bo=true;
	for(int j=0;j<n;j++){
		if(a[i][j]&&a[i][j]<min(c[i],c[j])&&b[j]<2){//i、j有重合部分&&不完全重合&&j的使用次数不多于2 
			b[j]++;
			sum+=(c[j]-a[i][j]);//加j单词长度，减去重合长度 
			bo=false;
			dfs(j);
			//回溯 
			sum-=(c[j]-a[i][j]);
			b[j]--;
		}
	}
	if(bo){
		max1=max(sum,max1);
	}
	return ;
}
int main(){
	int i,j,k,l;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>str[i];
		c[i]=strlen(str[i]);
	}
	cin>>ch;
	/*
	 *将i单词接j单词的最小重合长度存入a[i][j]
	 */ 
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			bool bo=true;
			int p=0;
			
			for(k=c[i]-1;k>-1;k--){
				for(l=k;l<c[i];l++)
				//从i单词的尾部比较 ，依次增加重合长度，直至重合 ，找到最小重合长度 
				    if(str[i][l]!=str[j][p++]){
				    	bo=false;
			    		break;
				    }
				    
				if(bo){
				    a[i][j]=c[i]-k;
			    	break;
			    }
			    p=0;
			    bo=true;
			}
		}
	}

	for(i=0;i<n;i++){
		if(str[i][0]==ch){
			b[i]++;
		    sum+=c[i];
	    	dfs(i);
	    	//回溯 
	    	sum-=c[i];
	    	b[i]--;
		}
	}
	cout<<max1<<endl;
	return 0;
}