数位DP HDU3555

Bomb

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 15025 Accepted Submission(s): 5427

Problem Description

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

Input

The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description.

The input terminates by end of file marker.

Output

For each test case, output an integer indicating the final points of the power.

Sample Input

Sample Output

0
1
15
Hint

From 1 to 500, the numbers that include the sub-sequence "49" are "49","149","249","349","449","490","491","492","493","494","495","496","497","498","499",
so the answer is 15.

Author

fatboy_cw@WHU

Source

2010 ACM-ICPC Multi-University Training Contest（12）——Host by WHU

Recommend

zhouzeyong | We have carefully selected several similar problems for you: 3554 3556 3557 3558 3559

题意：

1~nz中包含49的数有几个。

代码：

  1 /*
  2 本题与HDU2089相似，把那道题的代码改了一下找出了不含49的，然后用总数减去，简单粗暴，当然有更好的方法。
  3 */
  4 #include<iostream>
  5 #include<string>
  6 #include<cstdio>
  7 #include<cmath>
  8 #include<cstring>
  9 #include<algorithm>
 10 #include<vector>
 11 #include<iomanip>
 12 #include<queue>
 13 #include<stack>
 14 using namespace std;
 15 int t;
 16 long long dp[40][10],n;
 17 void init()
 18 {
 19     for(int i=1;i<22;i++)
 20     {
 21         for(int j=0;j<10;j++)
 22         {
 23             for(int k=0;k<10;k++)
 24             {
 25                 if(j==4&&k==9) continue;
 26                 dp[i][j]+=dp[i-1][k];
 27             }
 28         }
 29     }
 30 }
 31 long long insum(long long n)
 32 {
 33     long long sum=0;
 34     int lne=1,c[30]={0};
 35     while(n)
 36     {
 37         c[lne++]=n%10;
 38         n/=10;
 39     }
 40     for(int i=lne-1;i>0;i--)
 41     {
 42         for(int j=0;j<c[i];j++)   //j不能等于c[i],因为dp[i][j]中的j代表第i位取j时的总数，而j后面的数
 43                                   //要全部遍历一遍，这里j后面并非取全部数而是取到给出的数的后几位
 44         {
 45             if(j==9&&c[i+1]==4) continue;
 46             sum+=dp[i][j];
 47         }
 48         if(c[i]==9&&c[i+1]==4) break;
 49     }
 50     return sum;
 51 }
 52 int main()
 53 {
 54     scanf("%d",&t);
 55     while(t--)
 56     {
 57         memset(dp,0,sizeof(dp));
 58         dp[0][0]=1;
 59         cin>>n;
 60         n+=1;
 61         init();
 62         long long a=insum(n);
 63         cout<<n-a<<endl;
 64     }
 65     return 0;
 66 }
 67 
 68 /*
 69 别人的一个更好的方法。很难想到。
 70 */
 71 #include<iostream>
 72 #include<string>
 73 #include<cstdio>
 74 #include<cmath>
 75 #include<cstring>
 76 #include<algorithm>
 77 #include<vector>
 78 #include<iomanip>
 79 #include<queue>
 80 #include<stack>
 81 using namespace std;
 82 int t;
 83 long long dp[25][3],n; //dp[i][0]表示到第i位没有49的个数，dp[i][1]表示到第i位没有49但第i位是9的个数,
 84                        //dp[i]][2]表示到第i位包含49的个数。
 85 void init()
 86 {
 87     dp[0][0]=1;        //初始化
 88     dp[0][1]=0;
 89     dp[0][2]=0;
 90     for(int i=1;i<23;i++)
 91     {
 92         dp[i][0]=10*dp[i-1][0]-dp[i-1][1];  //到第i位没有49的个数等于第i位依次取0~9连上后面没有49的，
 93                                             //然后去掉第i位取4，i-1位为9的情况。
 94         dp[i][1]=dp[i-1][0];                //第i位是9时
 95         dp[i][2]=10*dp[i-1][2]+dp[i-1][1];  //到第i位包含49的个数等于第i位依次取0~9连上后面包含49的,
 96                                             //再加上第i位取4时，i-1位是9的情况。
 97     }
 98 }
 99 long long insum(long long n)
100 {
101     long long sum=0;
102     int c[23]={0};
103     int cnt=1;
104     while(n)
105     {
106         c[cnt++]=n%10;
107         n/=10;
108     }
109     bool flag=false;
110     for(int i=cnt-1;i>0;i--)   //从高位到低位依次枚举
111     {
112         sum+=dp[i-1][2]*c[i];           //到第i-1位包含49，就加上0~c[i]个
113         if(flag) sum+=dp[i-1][0]*c[i];
114         else
115         {
116             if(c[i]>4) sum+=dp[i-1][1];  //如果第i位大于4了，并且i-1是9，则一定包含49.
117         }
118         if(c[i+1]==4&&c[i]==9) flag=true; //当从高位出现49之后后面dp[i][0]就无意义了，全加上
119     }
120     return sum;
121 }
122 int main()
123 {
124     scanf("%d",&t);
125     {
126         while(t--)
127         {
128             scanf("%lld",&n);
129             init();
130             printf("%lld
",insum(n+1));  //计算结果不包含n本身
131         }
132     }
133     return 0;
134 }

 1 //记忆化搜索法
 2 #include<iostream>
 3 #include<string>
 4 #include<cstdio>
 5 #include<cmath>
 6 #include<cstring>
 7 #include<algorithm>
 8 #include<vector>
 9 #include<iomanip>
10 #include<queue>
11 #include<stack>
12 using namespace std;
13 long long n;
14 int t;
15 long long dp[40][3];
16 int c[40];
17 long long dfs(int lne,int have,int lim)
18 {
19     if(lne<=0)
20     return have==2;
21     if(!lim&&dp[lne][have]!=-1)
22     return dp[lne][have];
23     long long ans=0;
24     int nnum=lim?c[lne]:9;
25     for(int i=0;i<=nnum;i++)
26     {
27         int nhave=have;
28         if(have==0&&i==4) nhave=1;
29         if(have==1&&i!=4&&i!=9) nhave=0;
30         if(have==1&&i==9) nhave=2;
31         ans+=dfs(lne-1,nhave,lim&&i==nnum);
32     }
33     if(!lim)
34     dp[lne][have]=ans;
35     return ans;
36 }
37 int main()
38 {
39         scanf("%d",&t);
40         while(t--)
41         {
42             scanf("%lld",&n);
43             memset(dp,-1,sizeof(dp));
44             int cnt=0;
45             while(n)
46             {
47                 c[++cnt]=n%10;
48                 n/=10;
49             }
50             c[cnt+1]=0;
51             printf("%lld
",dfs(cnt,0,1));
52         }
53     return 0;
54 }