返回信息流题目大意:给出一组由小写字母和#组成的字符串,判断字符串是否存在连续三个元音或连续五个辅音的情况,#表示这个字母不能确定是什么..字符串长度不超过100
对于这道题,我们很容易想到的方法是枚举所有情况,然后对每种情况分别进行判断.但是,注意到字符串长度最大是100,也就是说最多可能有100个字符的情况不能确定,如果用枚举的方法,一个字符有两种情况(元音或辅音),那最多就会有2^100个状态,这绝对是一个天文数字.因此枚举的方法必然超时.
为了减少状态,我们可以考虑用记忆化搜索来解这道题,定义dp[i][j][k],表示当前搜索到第i个字符,这个字符属于元音还是辅音(j=0表示元音,1表示辅音),这种状态(元音或辅音)连续出现了k次。然后递归函数isgood(int i,int j,int k),isbad(int i,int j,int k)进行判断即可。。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #5261同步于 2007/3/18
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
[解题报告]Vitamin部落I -文字
xiaolonghing
2007/3/18镜像同步0 回复
订阅后，新回复会通过你的通知中心匿名送达。
0 条回复
暂无回复 · 你可以订阅本帖等待新回复。