看了许多题解都好长啊,自不量力的来贴一下代码
(震惊于这都能ac。。。)
这道题的思路是先从字符串中找有重部分然后直接比较剩下的部分,比较的数据也可以用来计算数值
其实满水的题
总之看注释啦(竟然能耐心的写完注释...)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<stack>
#include<cstring>
using namespace std;
int n,num;
string w[];//记录单词
int use[];//记录使用单词次数
int ans,now=;//记录接龙的长度,now=1是省略了头字母
void dfs(int k)//深搜
{
ans=max(ans,now);//跟上个题解学的,取大
for(int i=;i<=n;i++)//搜索每个单词
{
if(use[i]<)//判断
{
for(int j=;j<w[k].length();j++)//判断,如果首字母相同则比较
if(w[i][]==w[k][j])
{
int l1=j,l2=;
while(w[i][l2]==w[k][l1]&&l1<w[k].length())l1++,l2++;//比较至词尾
if(l1>=w[k].length())//如果比较完成
{
now+=w[i].length()-l2;//新单词减去与上个单词重合的长度
use[i]++;
dfs(i);//以这个单词为新节点搜索
now-=w[i].length()-l2;
use[i]--;
}
}
}
}
}
int main()
{
cin>>n;
for(int i=;i<=n;i++)
cin>>w[i];
cin>>w[];//**把头字母看做一个单词**
dfs();//**从头字母这个单词搜索**
cout<<ans;
return ;
}/*我无聊呀,无聊!一袋恰恰香瓜子,我一个人嗑完了,一共1869颗,21颗是空的,混进来9颗带虫的,还有6颗没炒开,是连在一起的,还有4个是苦的。中间喝了7杯水。没错,这就是孤独。…刚才这一段话一共67个字,11个标点符号,其中8个逗号,3个句号,一共有587划,其中横78划,竖137划,撇65划,捺57划,其他139划。没错这就是闲人的最高境界难过同意的来个赞赞?(?ε`) 顺便无聊一下*/