微商可以做网站推广吗,东莞网站建设地点优化,四川省城乡住房与建设厅网站,网络推广的方案怎么写题目链接
P1019 [NOIP2000 提高组] 单词接龙
细节
题目中描述的在两个单词相连时#xff0c;其重合部分合为一部分具有一定的误导性#xff0c;对于字符串 b e e bee bee 和 e e d eed eed #xff0c;合并之后的字符串为 b e e e d beeed beeed #xff0c;只有中间…题目链接
P1019 [NOIP2000 提高组] 单词接龙
细节
题目中描述的在两个单词相连时其重合部分合为一部分具有一定的误导性对于字符串 b e e bee bee 和 e e d eed eed 合并之后的字符串为 b e e e d beeed beeed 只有中间的 e e e 为重复部分。故应该求两个字符串的最小重叠长度这样才能构建一个最大长度的字符串。
思路
为何要使用深度优先搜索
为了求得最大长度的字符串需要多次遍历所有字符串每次有多种选择就像一颗不断发散的树枝一样这就需要使用深度优先搜索。
剪枝
假设有 n n n 个字符串每个字符串最多能两次添加到最终字符串里故时间复杂度为 O ( 2 n ∗ 2 n ) O ( 4 n 2 ) O(2n * 2n) O(4n^2) O(2n∗2n)O(4n2) 故需要使用剪枝来优化。假如两个字符串没有重叠部分则不再往深处搜索这就是剪枝。此外还应该定义一个数组 u s e [ ] use[] use[] 来表示字符串使用的次数如果使用次数等于两次则跳过当前字符串。
dfs函数的实现 d f s dfs dfs 函数用于在字符串数组 s t r s [ ] strs[] strs[] 中寻找给定字符串 s t r str str 的下一个待拼接的字符串而且还有一个参数 l e n N o w lenNow lenNow 表示当前已拼接的字符串的长度。
每次先更新答案如果 l e n N o w lenNow lenNow 更大就把 l e n N o w lenNow lenNow 赋值给答案。 然后在循环中判断 s t r s [ ] strs[] strs[] 中哪个字符串与 s t r str str 重叠如果能找到而且使用次数不超过两次就增加使用次数然后进行递归传入该字符串和新的拼接字符串的长度接着在回溯时减少使用次数(因为回溯时放弃使用该字符串)最后判断下一个符合要求的字符串直到找到最大长度。在实现中可以先判断使用次数是否超过两次这样减少了无效的判断重叠部分。
显然 d f s dfs dfs 函数需要另一个函数 g e t O v e r l a p L e n getOverlapLen getOverlapLen 来计算两个字符串重叠部分的最小长度这个函数很容易实现 先得到两个字符串 s 1 , s 2 s1, s2 s1,s2 的长度 l e n 1 , l e n 2 len1, len2 len1,len2 然后去较小值为 l i m lim lim l i m lim lim 用于防止数组下标越界。 每次循环中判断 s 1 s1 s1 的倒数第 j j j 个字符是否与 s 2 s2 s2 的第 j j j 个元素相等如果不相等就退出循环得到一个表示最大重叠长度 j j j 。 为了求得最小重叠长度需要再嵌套一层循环外层循环用于增加判断的字符数量 i i i 内层循环用于判断 s 1 s1 s1 的倒数第 j j j 个字符是否与 s 2 s2 s2 的第 j j j 个元素相等如果不相等就终止内层循环然后返回已判断为相等的字符数量 i i i 这点看代码会更好理解。
代码
#include iostream
#include string
using std::cin, std::cout, std::string;
const int N 25;// 字符串数组的大小
string strs[N];// 用于存放字符串
/*n是字符串的个数len是拼接字符串的长度use[i]表示下标为i的字符串使用的次数
*/
int n, len, use[N];
// 求s1和s2字符串的最小重叠长度
int getOverlapLen(string s1, string s2) {int len1 s1.length(), len2 s2.length(); // 求得s1和s2的长度int lim len1 len2 ? len1 : len2; // 求得s1和s2长度的较小值for (int i 1; i lim; i) { // 外层循环用于控制比较多字符长度bool isEqual true; // 判断两个字符串的重叠长度是否为ifor (int j 0; j i; j) { // 判断两个字符串的字符是否重叠if (s1[len1 - i j] ! s2[j]) { // 如果字符不重叠isEqual false; // 则两个字符串的重叠长度不为ibreak; // 中断内层循环}}if (isEqual) { // 如果两个字符串的重叠长度为ireturn i; // 返回i}}return 0; // 两个字符串没有重叠部分返回0
}
// 在字符串数组strs[]中寻找给定字符串str的下一个待拼接的字符串
void dfs(string str, int lenNow) {len len lenNow ? len : lenNow; // 更新拼接字符串的长度for (int i 0; i n; i) {if (use[i] 2) { // 如果当前字符串的使用次数等于两次continue; // 跳过当前字符串}// 获取 已拼接字符串 和 下标为i的字符串 的重叠长度int ol getOverlapLen(str, strs[i]);if (ol 0) { // 如果重叠长度大于0use[i]; // 使用下标为i的字符串// 寻找下一个待拼接字符串dfs(strs[i], lenNow strs[i].length() - ol);use[i]--; // 回溯时该字符串没被使用}}
}
int main() {cin n;for (int i 0; i n; i) {cin strs[i]; // 下标为n的字符串保存了指定开头的字母}dfs(strs[n], 1); // 开头为指定字母长度为1cout len;return 0;
}
