Bomb（数位Dp）

布满荆棘的人生 2022-08-03 00:09 218阅读 0赞

# Bomb #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)  
Total Submission(s): 10373    Accepted Submission(s): 3657**

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

3
    1
    50
    500

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

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #define ll long long
    using namespace std;
    ll dp[21][3];
    void init()
    {
        int i;
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        /*
        dp[i][0]代表长度为 i 并且不含有49的数字的个数；
    　　dp[i][1]代表长度为 i 并且不含有49，但是最高位是9的数字的个数；
    　　dp[i][2]代表长度为 i 并且含有49的数字的个数。
        */
        for(i=1;i<21;i++)
        {
            dp[i][0]=dp[i-1][0]*10-dp[i-1][1];// 表示长度为 i 的不含有49的数字的个数等于
           // 长度为 i - 1 的不含有49的数字的个数*当前的数字
            dp[i][1]=dp[i-1][0];//表示长度为 i 的并且不含有49同时最高位是9的数字的个数等于，
           //长度为 i - 1 的不含有49的数字的个数，
           //因为只要在它的高一位加上一个9就可以了。
            dp[i][2]=dp[i-1][2]*10+dp[i-1][1];
             /*
              表示长度为 i 的含有49的数字的个数等于，
              长度为 i - 1 的数字的个数*当前的数字
              ，再加上长度为 i - 1 的
              并且不含有49同时最高位是9的数字的个数，因为这个时候，
              只要在高一位加上一个4就可以了，
              这样在最高的两位就组成了一个49。*/
        }
    }
    int main()
    {
        int i,t,len,last,flag,a[22];
        ll ans,n;
        init();
        cin>>t;
        while(t--)
        {
            memset(a,0,sizeof(a));
            last=flag=ans=0;//flag用于判断这个数之前的数是否是49
            cin>>n;
            n++;
            len=1;
            while(n)
            {
                a[len++]=n%10;
                n/=10;
            }
            len--;
            for(i=len;i>=1;i--)
            {
                ans+=dp[i-1][2]*a[i];//在i之前的一位所有含有49数的种类*当前数
                if(flag)//如果这个数与前一个数组合成49
                {
                    ans+=dp[i-1][0]*a[i];//这个数的种类就是下一位所有的非49数*当前数
                    //比如4960，应该是6*1=6;
                }
                if(!flag&&a[i]>4)
                {
                    ans+=dp[i-1][1];
                }
                if(last==4&&a[i]==9)
                {
                    flag=true;
                }
                last=a[i];
            }
            printf("%I64d\n",ans);
        }
    }

因为后面的for循环求的是(0,n)的开区间的符合条件的数字的数目，题目要求\[1,n\]这个区间内的符合条件的数字的数目，所以要把区间的右端点加1。这样的处理方式比较方便，就不用判断这个端点是不是如何条件的数字了。