hdu3555 Bomb 数位DP入门

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3555

简单的数位DP入门题目

思路和hdu2089基本一样

直接贴代码了，代码里有详细的注释

代码：

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstdio>
 4 #include<cstring>
 5 using namespace std;
 6 long long int dp[30][3];
 7 void init()
 8 { 
 9         dp[0][0]=1;dp[0][1]=0;dp[0][2]=0;
10         for(int i=1;i<30;i++)
11             {
12                dp[i][0]=dp[i-1][0]*10-dp[i-1][1];//dp[i][0]表示长度为i的不含49的数的个数
13                dp[i][1]=dp[i-1][0];//dp[i][1]表示长度为i的不含49且最高位为9的数的个数
14                dp[i][2]=dp[i-1][2]*10+dp[i-1][1];// dp[i][2]表示长度为i的含49 的数的个数
15             }
16 }
17 int bit[30];
18 long long int solve(long long int n)
19 {
20   int len=1;
21   while(n)
22   {
23     bit[len++]=n%10;
24     n/=10;
25   }
26   bit[len]=0;
27   long long int ans=0;
28   bool flag=0;
29   for(int i=len;i>=1;i--)
30   {
31        ans+=dp[i-1][2]*bit[i];
32        if(flag) ans+=dp[i-1][0]*bit[i];//如果高位已经出现49那么后面随意
33        if(flag==0 && bit[i]>4) ans+=dp[i-1][1];
34        if(bit[i+1]==4 && bit[i]== 9) flag=1;
35 
36   }
37   if(flag ) ans++;
38   return ans;
39 }
40 int main()
41 {
42    int t;
43    long long int n;
44    scanf("%d",&t);
45    init();
46    while(t--)
47    {
48         scanf("%I64d",&n);
49 
50         cout<<solve(n)<<endl;
51    }
52    return 0;
53 }