洛谷-P1019 单词接龙（DFS有难度）¶

洛谷-P1019 单词接龙（DFS有难度）¶

题目描述¶

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beastbeast和astonishastonish，如果接成一条龙则变为beastonishbeastonish，另外相邻的两部分不能存在包含关系，例如atat 和 atideatide 间不能相连。

输入格式¶

输入的第一行为一个单独的整数nn (n \le 20n≤20)表示单词数，以下nn 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出格式¶

只需输出以此字母开头的最长的“龙”的长度

输入输出样例¶

输入 #1

5
at
touch
cheat
choose
tact
a

输出 #1

说明/提示¶

（连成的“龙”为atoucheatactactouchoose）

NOIp2000提高组第三题

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;

int n;
vector<vector<int> > overlap(25, vector<int>(25)); //预处理第i个单词开头和第j个单词的最小重叠长度
vector<string> word(25);
vector<int> freq(25); //统计每个单词的使用频率

int cur = 0, res = -1;

void calculate(int pos1, int pos2)
{
    int len1 = word[pos1].size(), len2 = word[pos2].size();
    int len = min(len1, len2);

    for (int i = 1; i <= len - 1; ++i) {
        if (word[pos1].substr(len1 - i) == word[pos2].substr(0, i)) {
            overlap[pos1][pos2] = i; break;
        }
    }
}

void DFS(int pos)
{
    bool haveChange = false;

    for (int i = 0; i < n; ++i) {
        //频率超过限制或者没有重叠的部分
        if (freq[i] >= 2 || overlap[pos][i] == 0) continue;
        cur += word[i].size() - overlap[pos][i];
        ++freq[i];
        haveChange = true;
        DFS(i);
        cur -= word[i].size() - overlap[pos][i];
        --freq[i];
    }
    //如果已经没有单词可以接下去，更新长度
    if (!haveChange) res = max(res, cur);
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> word[i];
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            calculate(i, j); //预处理计算重叠长度的最小值
        }
    }

    char ch;
    cin >> ch;

    for (int i = 0; i < n; ++i) {
        if (word[i][0] == ch) {
            ++freq[i];
            cur = word[i].size();
            DFS(i); //以第i个单词为开头开始搜索
            --freq[i];
            cur = 0;
        }
    }
    cout << res << endl;

    return 0;
}

还是很难得一道搜索题目，利用一个二维数组overlap来预先计算出两个字符串得重叠长度，长度得计算需要取两个字符串中较小的部分，然后从小打到去寻找最短重叠部分。搜索的过程是先找到起始单词，然后从这个单词开始深搜。深搜地过程中，需要去判断使用频率和重叠长度，用一个bool型变量来记录每次寻找是否能找到接下去地单词。