题解：P1019 [NOIP 2000 提高组] 单词接龙

SuyctidohanQ · 2025-02-18 16:23:28 · 题解

思路分析

UPD：修改了代码。

本题为搜索。考虑使用 dfs 枚举以指定字母开头的单词开始，连接所有可能的单词的单词串的长度。

注意还需要使用一个数组保证每个单词使用次数不超过 2 次。

代码实现

#include <bits/stdc++.h>
#define please return
#define AC 0
#define rep(i, a, b) for (int i = a; i <= b; i++)
using namespace std;
const int MAXN = 20 + 10;
string S[MAXN];
int n, ans = 0, cnt[MAXN];
char c;
int check (string x, string y) {
    string a = "", b = "";
    rep(i, 1, min (x.size (), y.size ()) - 1) { 
        a = x.substr (x.size () - i, i);
        b = y.substr (0, i);
        if (a == b) return i;   
    }
    return 0;
}

void dfs (string s, int len) {
    ans = max (ans, len);
    int x;
    rep(i, 1, n) {  
        x = check (s, S[i]);
        if (cnt[i] < 2 && x != 0) { 
            cnt[i] ++;

            dfs (S[i], len + S[i].size () - x);     
            cnt[i] --;

        }

    }

}
signed main (void) {
    cin >> n;
    rep(i, 1, n) cin >> S[i];
    cin >> c;
    rep(i, 1, n) {

        if (S[i][0] == c) {

            cnt[i] ++;
            dfs (S[i], S[i].size ());
            cnt[i] --;

        }

    }

    cout << ans << endl;

    please AC;
}