题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=5642
国王演讲后士气大增,但此时战争还没有结束,国王时不时要下发命令。 由于国王的口吃并没有治愈,所以传令中可能出现:“让第三军-军-军,到前线去” 这样的命令。由于大洋国在军队中安插了间谍 , 战事紧急,很多时候前线的指挥官不能分清哪些命令真正来自国王。但国王的命令有一个特点,他每次连续重复的字符最多 次. 所以说他的命令中没有:“让第三军-军-军-军 , 到前线去”,但是可以有 :“让第三军-军 , 到前线去” 。 此时将军找到了你,你需要告诉他,给定命令的长度长度为 ,有多少种不同的命令可以是国王发出的 。(也就是求长度为 的合格字符串的个数)当然,国王可能说出一句话没有犯任何口吃,就像他那次演讲一样。 为了简化答案,国王的命令中只含有小写英文字母,且对答案输出模 。 我们认为两个命令如果完全相同那么这两个字符串逐个比较就完全相同。
第一行一个整数表示测试组数:。 每组数据占一行,每行一个正整数 表示字符串的长度。
共 行,每行一个整数表示合法的命令数量。
2 2 4
676 456950
两个中没有不符合要求的,所以答案为 四个不符合要求的只有 `aaaa` `bbbb` ... `zzzz`总共 26 个 那么答案就是:
题解:
方法一:
dp[i][j]表示长度为i以字母j+‘a‘结尾的所有合法情况,现在我们先考虑所有情况再减去那些非法情况(以连续四个j结尾的状态为非法状态 ,超过四个j的之前一定已经考虑过了,这里不能再考虑进去)所以先预处理出i<=4的值,对于i>5,有如下转移方程:
dp[i][j]=∑dp[i-1][k]-( ∑dp[i-4][k](k!=j) )
代码1:
1 #include<iostream>
View Code
原文:http://www.cnblogs.com/fenice/p/5284507.html