bc #75 C || hdu 5642 King’s Order (数位dp)

hdu5642题目链接
题意:问长度为n的仅由26个小写字母组成的合法字符串有多少个。如果某个字符连续出现四次或以上,则这个字符串为非法。否则为合法。

思路:当时以为是组合数学的题。。。推了半天公式还是还是gg…
现在学了数位dp..果然是数位dp里很简单的一种。。。
dp[i][j][k]表示长度为i,最后一个字符对应的数字为j,最后一个字符出现了k次的方案数。

需要注意的是,这种连续几个位置相等或者不相等什么的。。。没有必要维护具体那些位置上的字符是什么。。。所以这种只统计最后一个字符,以及最后一个字符出现的次数的方法具有普遍意义。。注意理解。。。

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz