| 题目名称 | 374. 单词游戏 |
|---|---|
| 输入输出 | words.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2009-09-02加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：29， 提交：151， 通过率：19.21% | ||||
 Des. |
100 | 0.003 s | 0.12 MiB | Pascal |
 Makazeu |
100 | 0.003 s | 0.26 MiB | C++ |
 belong.zmx |
100 | 0.004 s | 0.12 MiB | Pascal |
 TBK |
100 | 0.004 s | 2.84 MiB | C++ |
 ConanQZ |
100 | 0.007 s | 0.30 MiB | Pascal |
 再见 |
100 | 0.031 s | 0.32 MiB | C++ |
 kaaala |
100 | 0.062 s | 0.27 MiB | C++ |
|
再见 |
100 | 0.084 s | 0.31 MiB | C++ |
 FoolMike |
100 | 0.086 s | 0.19 MiB | Pascal |
 白&夜 |
100 | 0.091 s | 0.33 MiB | C++ |
| 关于 单词游戏 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
第一个点要上天
所以对于输入N=500的直接输出5就好了23333333333  rvalue
2017-03-04 09:19
9楼
| ||||
|
回复 @Truth.Cirno :
求教剪枝是什么，联系方式QQ：814439229  浅若&清风
2016-11-02 21:47
8楼
| ||||
|
第一组数据什么玩意……
 水中音
2015-11-30 13:11
7楼
| ||||
|
！！！为什么我数出的所有数据评测机都说我输出了10！！！而且在下面测全是对的！！！求解！！！
 小DOTA
2014-12-07 21:07
6楼
| ||||
|
第一个测试点是啥情况？
| ||||
|
添加分类：贪心
| ||||
|
经研究CH、LC等大神程序发现了剪枝的方法（贪心减枝），可应对满足题意的所有类型的数据（题库数据其实不全面）：（前提：把“A E I O U”作为节点，即图的节点最多五个）
通过深搜枚举所有情况时，对于“这样的”若干条路（这样的：这几条道路出发点一样，结束点一样，均未被用过） 只走那一条最长的路，其他的路不需要走了，是多余的 （此处“多余”的定义：1、枚举出来的解不是最优解；2、枚举出来的解出现重复） | ||||
|
给个变态数据（本人未过）：
.in 16 AA AA OI OI OI OI OI OI OI IO IO IO IO IO IO IO .out 28 | ||||
|
算是偷懒的预处理？
--->把自环由N个缩为了一个。（视A E I O U为节点） | ||||
Truth.Cirno【问题描述】
慧慧和南南在玩一个单词游戏。
他们轮流说出一个仅包含元音字母的单词，并且后一个单词的第一个字母必须与前一个单词的最后一个字母一致。
游戏可以从任何一个单词开始。
任何单词禁止说两遍，游戏中只能使用给定词典中含有的单词。
游戏的复杂度定义为游戏中所使用的单词长度总和。
编写程序，求出使用一本给定的词典来玩这个游戏所能达到的游戏最大可能复杂度。
【输入格式】
输入文件的第一行，表示一个自然数N（1≤N≤16），N表示一本字典中包含的单词数量。以下的每一行包含字典中的一个单词，每一个单词是由字母A，E，I，O和U组成的一个字符串，每个单词的长度将小于等于100，所有的单词是不一样的。
【输出格式】
输出文件仅一行，表示该游戏的最大可能复杂度。
【输入样例】
5 IOO IUUO AI OIOOI AOOI
【输出样例】
16