题目描述
科协里最近很流行数字游戏。
某人命名了一种不降数,这种数字必须满足从左到右各位数字呈非下降关系,如 123,446。
现在大家决定玩一个游戏,指定一个整数闭区间 [a,b],问这个区间内有多少个不降数。
输入格式
输入包含多组测试数据。
每组数据占一行,包含两个整数 a 和 b。
输出格式
每行给出一组测试数据的答案,即 [a,b] 之间有多少不降数。
数据范围
1≤a≤b≤231−1
样例
输入样例:
1 9
1 19
输出样例:
9
18
算法1
(dfs)
利用类似前缀和的思想 [a, b]范围满足要求的数=[0,b]范围满足要求的数 - [0,a-1]范围满足要求的数
所以我们可以封装求[0, x]满足要求的数字为一个函数即可
一个数字x, 最右边当成第一位,数字长度为len的话,最左侧就为第len位,把他们存储到a数组中。
从最左侧开始搜索, pos记录枚举哪一位了, 需要记录前一位数字pre,pre如果比当前枚举的数字i大的话,就continue不予统计。
需要用一个limit记录当前位能枚举的上界,比如19 这个2位数,最左侧一位能枚举的范围是0-1, 不能超过1,
如果limit为false当前位能枚举到9,否则只能到最大a[pos]
dfs的含义就是从左往右枚举每一位,看是否符合要求。
为了优化,记忆化即可,需要注意有limit的情形不能用记忆化,比如求 132以内满足要求的数字,
枚举到第二位达到3时(13?), dp[2][3]表示2位数,最左侧以3开头,33~39都符合要求(133~139),所以dp[2][3]=7。但132的第一位的上界是2,不能超过这个数字,所以不能用记忆化的结果,应该返回0。
时间复杂度
< 数字位数 * 10 ?
参考文献
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
int dp[32][10];
int a[32];
int len;
int dfs(int pos, int pre, bool limit) {
if (!pos) return 1;
if (!limit && dp[pos][pre] != -1) return dp[pos][pre];
int cnt = 0, up_bound = (limit ? a[pos] : 9);
for (int i = 0; i <= up_bound; i ++) {
if (pre > i) continue;
cnt += dfs(pos - 1, i, limit && i== a[pos]);
}
return limit? cnt : dp[pos][pre] = cnt;
}
int solve(int x){
len = 0;
memset(dp, -1, sizeof(dp));
while (x) {
a[++len] = x % 10;
x /= 10;
}
return dfs(len, 0, true);
}
int main() {
int a, b;
while (cin >> a >> b) {
cout << solve(b) - solve(a-1) << endl;
}
return 0;
}