社区讨论

求助大佬

P1019[NOIP 2000 提高组] 单词接龙(疑似错题)参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lyl8o418
此快照首次捕获于
2024/07/14 15:33
2 年前
此快照最后确认于
2024/07/14 16:45
2 年前
查看原帖
用的传统char二维数组,蒟蒻求助
CPP
#include <bits/stdc++.h>
#define MAXN 61
using namespace std;
char word[21][MAXN];
int n,t[21],l[21],d[MAXN],ans,li[21][21];//li存放串的长度
char in[21][21];//记忆化搜索 
int isli(int a,int b)
{
	if(li[a][b])
	return li[a][b];
	for(int i=0;i<l[b];++i)
	{
		if(word[b][i]==word[a][l[a]-1])
		{
			bool ok=1;
			for(int q=1;q<i;++q)
			{
			//	printf("a:%c b:%c\n",word[b][i-q],word[a][l[a]-q-1]);
				if(word[b][i-q]!=word[a][l[a]-q-1])
				{
					ok=0;
					break; 
				}
			}
			if(ok)
			{
			//	printf("a-b:%d\n",i+1);
				li[a][b]=i+1;
				return i+1; 
			}
		}
	}
	return 0; 
} 
bool isin(int a,int b)
{
	return li[a][b]==l[a]||li[a][b]==l[b];
}//判断相邻是否包含 

void dfs(int cur,int tot)
{
	bool no=1;
//	printf("%s",word[cur]);
	for(int i=1;i<=n;++i)
	{
		if(t[i]&&isli(cur,i)&&!isin(cur,i))
		{
			no=0;//还能拓展 
			t[i]-=1;
			dfs(i,tot+l[i]-li[cur][i]);
			t[i]+=1;//回溯 
		}
	}
	if(no)
	{
		ans=max(ans,tot);
	}
}
int main()
{
	scanf("%d",&n);
	getchar();
	for(int i=1;i<=n;++i)
	{
		t[i]=2;
		in[i][i]=1;
		int q=0;
		char c;
		for(c=getchar();c!='\n';c=getchar())
		{
			word[i][q++]=c;
		}
		l[i]=q;
	}
	char c=getchar();
	for(int i=1;i<=n;++i)
	{
		if(word[i][0]==c)
		{
			t[i]=1;
			dfs(i,l[i]);
			t[i]=2;
		}//huisu
	}
	printf("%d",ans);
 } 

回复

0 条回复,欢迎继续交流。

正在加载回复...