科协里最近很流行数字游戏。 某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 123123，446446。 现在大家决定玩一个游戏，指定一个整数闭区间 [a,b][a,b]，问这个区间内有多少个不降数。 输入格式 输入包含多组测试数据。 每组数据占一行，包含两个整数 aa 和 bb。 输出格式 每行给出一组测试数据的答案，即 [a,b][a,b] 之间有多少不降数。 数据范围 1≤a≤b≤231−11≤a≤b≤231−1 输入样例： 1 9 1 19
输出样例： 9 18
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 15; int f[N][N]; void init(){ for (int i = 0; i <= 9; i ++) f[1][i] = 1; for (int i = 2; i <= N; i ++) for (int j = 0; j <= 9; j ++) for (int k = j; k <= 9; k ++) f[i][j] += f[i - 1][k]; } int dp(int n){ if (!n) return 1; vector<int> nums; while(n) nums.push_back(n % 10), n /= 10; int res = 0; int last = 0; for (int i = nums.size() - 1; i >= 0; i --){ int x = nums[i]; for (int j = last; j < x; j ++) res += f[i + 1][j]; if (x < last) break; last = x; if (!i) res ++; } return res; } int main(){ init(); int l, r; while(cin >> l >> r) cout << dp(r) - dp(l - 1) << endl; return 0; }