社区讨论
求助大佬
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 条回复,欢迎继续交流。
正在加载回复...