1 条题解
-
0Guest LV 0 MOD
-
1
#include <iostream> #include <algorithm> #include <cstring> using namespace std; long long int n, m; int a[20], dp[20][10]; //a用来存放数字的每位数 int dfs(int pos, int pre, bool limit) { //pre表示pos位数的下一位数的值,例如pos=3表示当前位为百位,则pre表示十位数的值 if (pos == 0) return 1; if (!limit && dp[pos][pre] != -1) return dp[pos][pre]; int ans = 0; int up = limit ? a[pos] : 9; for (int i = 0; i <= up; i++) { if (i < pre) continue; ans += dfs(pos - 1, i, i == a[pos] && limit); //从数字的高位向低位递归,新limit的取值根据原limit和i的取值决定,例如246,当pos表示十位数时,如果原limit=1(百位数=2)并且十位数等于4,那么下一次的搜索就会有限制(个位数上界限制为6) } // if(!limit) dp[pos][pre] = ans; return ans; } int solve(int x) { int pos = 0; //pos用于记录当前位数 while (x) { a[++pos] = x % 10; //pos从1开始表示位数从个位到高位 x /= 10; //如246在数组中的存放方式是6 4 2 } return dfs(pos, 0, 1); //从数字的最高位开始 } int main() { while (cin >> n >> m) { memset(dp, -1, sizeof(dp)); cout << solve(m) - solve(n - 1) << endl; //减的是n-1不是n,n自身要算进去 } return 0; }
- 1