hdu2089 不要62 数位dp

hdu2089 不要62

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int dp[15][15], d[15];
 4 void init() {
 5     dp[0][0] = 1;
 6     for (int i = 1; i <= 7; i++) {
 7         for (int j = 0; j <= 9; j++) {
 8             for (int k = 0; k <= 9; k++) {
 9                 if (j != 4 && !(j == 6 && k == 2)) {
10                     dp[i][j] += dp[i-1][k];
11                 }
12             }
13         }
14     }
15 }
16 int solve(int n) {
17     int ans = 0, len = 0;
18     while (n) {
19         ++len;
20         d[len] = n%10;
21         n /= 10;
22     }
23     d[len+1] = 0;
24     for (int i = len; i >= 1; i--) {
25         for (int j = 0; j < d[i]; j++) {
26             if (d[i+1] != 6 || j != 2) {
27                 ans += dp[i][j];
28             }
29         }
30         if (d[i] == 4 || (d[i+1] == 6 && d[i] == 2)) {
31             break;
32         }
33     }
34     return ans;
35 }
36 int main() {
37     init();
38     int l, r;
39     while (cin >> l >> r && (l||r)) {
40         cout << solve(r+1)-solve(l) << endl;
41     }
42     return 0;
43 }