当前位置:首页 > 动态规划 > 数位DP > 正文
SSOJ2866数字游戏
533+

题目大意:在区间[a, b]中有多少个数字是逐位不递减的?

题目描述

科协里最近很流行数字游戏。某人命名了一种不降数,这种数字必须满足从左到右各位数字成小于等于的关系,如 123,446。现在大家决定玩一个游戏,指定一个整数闭区间 [a,b],问这个区间内有多少个不降数。

输入

有多组测试数据。每组只含两个数字 a,b,意义如题目描述。

输出

每行给出一个测试数据的答案,即 [a,b] 之间有多少不降数。

样例输入

1 9
1 19

样例输出

9
18

对于全部数据,$1≤a≤b≤2^{31}−1$。

解题思路

本题数据范围比较小,可以直接暴力通过。

程序实现

需要求区间[x, y]每一位不递减的数字的数量,可以暴力填这些数字的每一位,每得到一个数字,如果满足区间范围则加1。

递归结束条件:超过y。时间复杂度约$O(10!)$

写成数位DP的形式,可以进行剪枝。

首先区间[x, y]中符合要求的数字个数,可以转成前缀和:前y个符合要求的数量减去前x-1个符合要求的数量。

对于前n个符合要求的数量,我们可以把n逐位取出,然后填数字的时候,就可以根据该位的值进行剪枝。

从高位开始,如果之前的位都是相等(没有超过n),那么下一位不能比对应位大,否则可以填到9。

注意,最高位可以填零,即相当于位数少的数字。

加入记忆化,就是数位DP了!f[k][x][p]表示从高位开始填,第k位填x时比原数小(p为真则小,否则高位全部相等)的后面填法的方案数。

后面的填法,取决于是否比原数大,从几开始填,以及剩下多少位,这些都确定了,那么后面的如果搜索过就可以记下来,下次直接返回。

更多

About

坚决不Copy代码!

本文标签:,,,,,,,

SSOJ2866数字游戏:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter