P1019 单词接龙(C++

2024-07-13 14:05| 来源: 网络整理| 查看: 265

题目描述

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

输入格式

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

输出格式

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

输入输出样例输入 #1

5 at touch cheat choose tact a

输出 #1

说明/提示

（连成的“龙”为atoucheatactactouchoose）

NOIp2000提高组第三题

反思

这个题真的反思良多，递归一直是我的弱项，而以递归为基础的DFS更是心病，解这道题所遇到的问题或反思且听我细细道来：

1. 数据结构

别总就想着用那些现成的容器，就拿vector来说，确实很方便可是数组或字符串一样可以啊，用了vector以后，各个函数的接口处的数据类型转换会磨完你的信心；

2.函数接口

在写算法的时候不要纠结于各个细节函数的实现，如果在写算法的时候需要某项功能，请先假设此功能函数已实现，并想清楚在此算法中该函数到底需要什么参数和返回值，函数的接口很重要，先完成算法，再写功能函数，先整体后局部，不然具体功能函数的实现会打断算法的思路！

3.深度优先搜索中的回溯

回溯之后会不会又走进这个分支？这不就是死循环了么？显然没有！那么回溯之后又没有标记，电脑是怎么知道该换分支了呢？答案就在dfs函数中的for循环上， for循环的i值一直在变，这本身就是一种标记了！（刚开始写回溯算法的时候没写循环可真是愁死个人~）

源码 #include using namespace std; class nodee { public: nodee():num(0){}//构造函数，顺便初始化num string vel; int num;//每个单词最多使用两次 }; nodee a[21]; int n, maxx = 1; int findd(string a, string b)//输出最少重复 { for (int i = 1; i flag = 0; break; } if (flag) return i; } return 0; } int dfs(string s, int len)//深度优先搜索 { int same = 0; for (int i = 0; i a[i].num++; len += a[i].vel.size() - same; dfs(a[i].vel, len);//递归 len -= a[i].vel.size() - same;//回溯 a[i].num--; } } maxx = max(maxx, len);//更新最大长度 return maxx; } int main() { cin >> n; for (int i = 0; i > a[i].vel;//a[n].vel为开头字母 dfs(a[n].vel, 1); cout

【本文地址】

公司简介

联系我们