站外题求助

题目总版

shx2011 @ 2024-11-09 23:13:21

题目大意

有 n 个单词（ 1≤n≤50 ），每个单词由 2个小写字母组成，并约定第 1 个单词为龙头。当2个单词形如ab-bc时称为可以接龙求最长接龙长度

如8个单词: aa ac ab de bh hk cd af

最长接龙长度为 4（aa-ac-cd-de）

给定n个单词求最长接龙长度

我的做法

dp,dp[i]为以i结尾的最长接龙长度

对于dp[i]，遍历它之前的每一个可接龙的字符串，找到最长的接龙

~~好像没啥问题对吧但是~~ WA了

WA code

#include<bits/stdc++.h>//dp为啥WA啊 
using namespace std;
int n,ans;
string s[60];
int dp[60];
bool check(string t,string x){
    if(t[1]==x[0]) return 1;
    return 0;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    dp[1]=1;//dp[i]:以i结尾的最大接龙长度 

    for(int i=2;i<=n;i++){
        int sum=1;
        for(int j=i-1;j>=1;j--){
            string t=s[j];
            if(check(t,s[i])){
                sum=max(sum,dp[j]+1);//从前面的能接龙的字符串中选一个接龙后长度最大的数 
            }
        }
        dp[i]=sum;
        ans=max(ans,dp[i]);
    }

    //for(int i=1;i<=n;i++) cout<<dp[i]<<" ";  
    //cout<<check(s[1],s[2]);
    cout<<ans;
    return 0;
}

by Jason20090916 @ 2024-11-09 23:56:18

是否会存在例如\ aa ac ef de bh hk cd af\ 即 aa-ac-cd-de-ef 的情况

或 aa ac cb ba 然后 aa-ac-cb-ba-aa 的循环情况

by shx2011 @ 2024-11-10 08:04:20

@Jason20090916 就是说选词可以不按输入循序？

by shx2011 @ 2024-11-10 08:05:05

@Jason20090916 ~~那这玩意咋做啊TuT~~

by Yi_chen123 @ 2024-11-10 13:35:39

能考虑改用DFS + 排列组合吗?不确定是否能AC

by Jason20090916 @ 2024-11-10 14:22:16

@shx2011 试一下 dfs + 回溯

by Jason20090916 @ 2024-11-10 14:23:17

@Jason20090916 递归边界就为最大值 = n（题意应该是想说每个单词最多用一次）

by Yi_chen123 @ 2024-11-10 20:23:43

是否考虑一下这份代码?初步判断好像没有什么问题

#include<bits/stdc++.h>
using namespace std;
struct Word{ //定义单词结构体
    char head; //头
    char tail; //尾
};

Word w[55]; //单词数组
bool b[55]; //每个单词是否被访问过
int ans = 0; //最终的答案
int n; //单词的总个数

//参数k为选取的单词下标
//参数cnt为当前单词接龙的长度
void dfs(int k, int cnt){//深搜,排列组合
    ans = max(ans, cnt);
    for(int i = 1; i <= n; ++i){
        if(!b[i] && w[i].head == w[k].tail && i != k){
            b[i] = true; //标记该单词被使用过
            dfs(i, cnt + 1); //递归深入
            b[i] = false; //回溯
        }
    }
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> w[i].head >> w[i].tail; //输入
    b[1] = true; //由于约定第1个单词为龙头,所以标记第1个单词被使用过
    dfs(1, 1); //深搜递归函数
    cout << ans; //输出最终结果
    return 0;
}