CodeForces - 1327E（dp）
给定n（n < 2 * 105），统计从 0 到 10n-1的所有数字（有前导零）中，统计不同长度的数字块的个数。
举个栗子：
9987654321 和 1999999999 两个数字中
len = 1 的数字块的个数为：9（前边那个数里有八个，后边有一个）
len = 2 的数字块的个数为：1
len = 9 的数字块的个数为：1
分析
先考虑最特殊的情况 n = len = x的时候，也就是n个数字全部相同，显然不管x取值为多少答案都是10
eg：x = 3 时，len = 3 的情况有：
000，111，222，333，444，555，666，777，888，999
也就是说 （n=1，len=1）与（n=2.len=2）与（n=3，len=3）与（n=x，len=x）全部都是等价的
进而我们去想，还有没有其他的等价关系，比较容易想到的是（n=i，len=j）与（n=i-1，len=j-1）是等价的
举个栗子：（n=4，len=3）可以当作（n=3，len=2）中，每个块都再插入一个和这个块相同的数字对应关系如下：
331 -->> 3331
332 -->> 3332
333 -->> 3333
334 -->> 3334
335 -->> 3335
336 -->> 3336
337 -->> 3337
338 -->> 3338
339 -->> 3339
330 -->> 3330………… 列举一部分
到这里是不是就应该有这样一种奇妙想法（DP），如下图
原创文章 3获赞 5访问量 690
关注
私信
展开阅读全文
作者：mldl_
