_Phoebe__
2022-01-23 22:57
采纳率: 96.9%
浏览 24

洛谷p1019 不知道哪里错了 想知道怎么改

P1019 [NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 https://www.luogu.com.cn/problem/P1019

 
#include<bitsdc++.h>
using namespace std;
int n;
int ans=0;
string word[999];
string beginword;
int used[999];//记录dfs时每个单词被使用了几次 
bool check(string s,string m,int k){//判断接口可行性,k代表接口长度 
 int len=s.length();
 for(int i=0;i<k;i++){
    if(s[len-k+i]!=m[i]){//s串的接口最开始应该是lens-k处然后在后面加上一个枚举的i就可以保证扫描到所有接口字符
        return false;
     }
     return true;
 }
}
void add(string &s,string m,int k){
    int lenm=m.length();
    for(int i=k;i<lenm;i++){
        s+=m[i];
    }
}
void dfs(string begin){
    int x=begin.length();
    ans=max(ans,x);//每次拼接后 更新一下答案 
    for(int i=0;i<n;i++){
        if(used[i]>=2)//如果一个单词用完了 就不能再用了 
        continue;
    int k_max=word[i].length();
    for(int j=0;j<k_max;j++){//枚举接口长度 
        if(check(begin,word[i],j)){
            string temp=begin;//使用字符串副本进行拼接 
            add(temp,word[i],j);
            if(temp==begin)
            continue;
            used[i]++;
            dfs(temp);
            used[i]--;//回溯 
            }
            }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>word[i];
    }
    cin>>beginword;
    dfs(beginword);
    cout<<ans<<endl;
    return 0;
}
//样例都过不了 不知道哪里错了 谢谢大家
 

2条回答 默认 最新

相关推荐 更多相似问题