2016多校训练Contest5:1007 K-wolf Number

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5787

题目翻译

求 l ~ r 中有多少个数字满足任意连续 K 个数字两两不相同。

题解

数位DP
我们用 F[i][used][1/0] 表示,1 ~ X中,现在DP到了从右往左数第 i 位,左边当前只用情况是 used ,高位是否和X一直相等 的情况下有多少个数字 。 ( used 不仅要记录使用了哪些数字,还要记录这些数字的顺序)
然后我们枚举当前位的可行转移,顺着转移就行了。如果高位和 X 相等,我们要注意转移不能是数字大于 X ,若不等,即可随便转移。
推荐记忆化搜索写

代码