hdu 3555 数位dp *

题意:求包含49的数字，先求不包含的，然后减一下就行了

链接：点我

如果不懂这种数位dp代码，可以看我博客dp专题里的初探数位dp

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define MOD 1000000007
10 const int INF=0x3f3f3f3f;
11 const double eps=1e-5;
12 typedef __int64 ll;
13 #define cl(a) memset(a,0,sizeof(a))
14 #define ts printf("*****
");
15 const int MAXN=105;
16 int n,m,tt;
17 ll dp[MAXN][2];    //0表示前面不为4
18 int digit[MAXN];
19 ll dfs(int p,int s,bool e) {
20     if (p==-1) return 1;
21     if (!e &&dp[p][s]!=-1) return dp[p][s];
22     ll res = 0;
23     int u = e?digit[p]:9;
24     for (int i=0;i<=u;++i)
25     {
26         if(s==1&&i==9)  continue;
27         res+=dfs(p-1,i==4,e&&i==u);
28     }
29     return e?res:dp[p][s]=res;
30 }
31 ll solve(ll n)
32 {
33     int len=0;
34     while(n)
35     {
36         digit[len++]=n%10;
37         n/=10;
38     }
39     return dfs(len-1,0,1);
40 }
41 int main()
42 {
43     int i,j,k;
44     #ifndef ONLINE_JUDGE
45     freopen("1.in","r",stdin);
46     #endif
47     scanf("%d",&tt);
48     ll x;
49     memset(dp,-1,sizeof(dp));
50     while(tt--)
51     {
52         scanf("%I64d",&x);
53         printf("%I64d
",x-solve(x)+1);
54     }
55 }