夏天做哪些网站能致富,福建网站建设服务,什么是响应式网站设计,网站刷流量有用吗单词游戏
传送门
题目描述
Io 和 Ao 在玩一个单词游戏。
他们轮流说出一个仅包含元音字母的单词#xff0c;并且后一个单词的第一个字母必须与前一个单词的最后一个字母一致。
游戏可以从任何一个单词开始。
任何单词禁止说两遍#xff0c;游戏中只能使用给定词典中含有…单词游戏
传送门
题目描述
Io 和 Ao 在玩一个单词游戏。
他们轮流说出一个仅包含元音字母的单词并且后一个单词的第一个字母必须与前一个单词的最后一个字母一致。
游戏可以从任何一个单词开始。
任何单词禁止说两遍游戏中只能使用给定词典中含有的单词。
游戏的复杂度定义为游戏中所使用的单词长度总和。
编写程序求出使用一本给定的词典来玩这个游戏所能达到的游戏最大可能复杂度。
输入格式
输入文件的第一行表示一个自然数 N ( 1 ≤ N ≤ 16 ) N(1 \le N \le 16) N(1≤N≤16) N N N 表示一本字典中包含的单词数量以下的每一行包含字典中的一个单词每一个单词是由字母 A、E、I、O 和 U 组成的一个字符串每个单词的长度将小于等于 100 100 100所有的单词是不一样的。
输出格式
输出文件仅有一行表示该游戏的最大可能复杂度。
样例 #1
样例输入 #1
5
IOO
IUUO
AI
OIOOI
AOOI样例输出 #1
16注明 以上来自洛谷。 以上来自洛谷。 以上来自洛谷。
解题思路
直接找题意做即可。循环遍历每一个字符串将其设为第一个字符串然后暴搜就行了。注意当搜索次数达到 5 × 1 0 7 5\times 10^7 5×107 时直接输出答案并结束程序。说起来有点抽象结合代码容易理解。
AC Code
#includebits/stdc.h
using namespace std;
int n;
string s[20];
int _s[20];
bool vis[20];
int COUNT;
int Answer;
inline void dfs(int len, char c) {COUNT;if (COUNT 5e7)cout Answer, exit(0);Answer max(Answer, len);for (register int i 1; i n; i) {if (vis[i])continue;if (s[i][0] c) {vis[i] 1;dfs(len _s[i], s[i][_s[i] - 1]);vis[i] 0;}}
}
signed main() {cin n;for (register int i 1; i n; i)cin s[i], _s[i] s[i].size();for (register int i 1; i n; i) {vis[i] 1;dfs(_s[i], s[i][_s[i] - 1]);vis[i] 0;}cout Answer endl;return 0;
}闲话
一开始以为这题非常简单没想到这么简单。注意到洛谷难度评级为 #!(#(!$(!#()*%%#Y%%%#%!-开启词汇联想
大佬 C Wx 用状压 DP 通过本题牛炸了。
