hdu 3555 bomb 数位dp

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mem1(a) memset(a, -1, sizeof(a))
 4 #define ll long long
 5 ll dp[20][20], digit[20];
 6 int len;
 7 ll dfs(int len, bool state, bool fp) {     //state表示这一位是否有限制
 8     if(!len)                                //fp表示len这一位是否只能取到小于等于digit[len]的数
 9         return 1;
10     if(!fp && dp[len][state]!=-1)
11         return dp[len][state];
12     ll ret = 0, maxx = fp?digit[len]:9;
13     for(int i = 0; i<=maxx; i++) {
14         if(i==9&&state)
15             continue;
16         ret += dfs(len-1, i==4, fp&&i == maxx); //对于这一题， 当这一位为6的时候， 下一位就会有限制
17     }
18     if(!fp)
19         return dp[len][state] = ret;
20     return ret;
21 }
22 ll cal(ll n) {
23     len = 0;
24     ll tmp = n;
25     while(n) {
26         digit[++len] = n%10;
27         n/=10;
28     }
29     return tmp-dfs(len, false, true);
30 }
31 int main()
32 {
33     int t;
34     ll b;
35     cin>>t;
36     while(t--) {
37         scanf("%I64d", &b);
38         mem1(dp);
39         printf("%I64d\n", cal(b)+1);
40     }
41 }