HDU 3555 Bomb (数位DP)

Bomb

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


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

 

题意:

给定一个数n,求[1,n]中含有"49"的数的个数。

 

思路:

首先我们考虑一个数中有无"49"的几种情况。(假设*中不包含"49")

1. ***49****
2. *********
3. 9********
4. 49*******

其实1和4是一样的情况,对于3,我们只需要在最高位添加一个4便组成一个含有"49"的数字,而对于2,数字中不包含"49"。

 

状态转移:

dp[i][0]代表长度为 i 并且不含有"49"的数字的个数;
dp[i][1]代表长度为 i 并且不含有"49"且高位是9的数字的个数;
dp[i][2]代表长度为 i 并且含有49的数字的个数。

 

数组 a[i] 从低位到高位存储 n 的每一位数字。

  • dp[i][0] = dp[i-1][0] * a[i] - dp[i-1][1];  表示长度为 i 的不含有49的数字的个数,它等于长度为 i - 1 的不含有49的数字的个数*当前位的数字,因为这个位置可以填0~a[i] - 1,然后再减去长度为 i - 1 的最高位是9的数字的个数,因为如果长度为 i - 1 的最高位是9的话,那么高一位就不能填4了,否则就组成了49。
  • dp[i][1] = dp[i-1][0]; 表示长度为 i 的并且不含有49同时最高位是9的数字的个数,它等于长度为 i - 1 的不含有49的数字的个数,因为只要在它的高一位加上一个9就可以了。
  • dp[i][2] = dp[i-1][2] * a[i] + dp[i-1][1]; 表示长度为 i 的含有49的数字的个数,它等于长度为 i - 1 满足条件的数字的个数*当前的数字,再加上长度为 i - 1 的不含有49并且最高位是9的数字的个数,因为这个时候,只要在高一位加上一个4就可以了,这样在最高的两位就组成了一个49。

 

然后我们可以从一个数的最高位开始枚举,首先要加上低一位满足条件数字的个数,如果当前位大于4,还要加上低一位最高位是9且不包含49的数字的个数,因为这种情况下只要我们把当前位设为4便可满足要求。

如果枚举位过程中已经遇到过49,则以后的枚举加上不含有49的数字个数,因为49已经出现过了,所以这样的组合依然满足题意。

 

AC代码:

#include <iostream>
#include<cstdio>
using namespace std;
#include<algorithm>
#include<string.h>
typedef __int64 LL;

LL dp[21][3];
int a[21];
void init() //预处理长度为i位dp[i][]的值
{
    dp[0][0]=1;
    for(int i=1; i<21; i++)
    {
        dp[i][0]=dp[i-1][0]*10-dp[i-1][1];  //长度为 i 并且不含有49的数字的个数
        dp[i][1]=dp[i-1][0];    //长度为 i 并且不含有49且高位是9的数字的个数
        dp[i][2]=dp[i-1][2]*10+dp[i-1][1];  //长度为 i 并且含有49的数字的个数
    }
}
void solve(LL n)
{
    int len=0;
    while(n)    //整数n分解每一位
    {
        a[++len]=n%10;
        n/=10;
    }
    LL ans=0;
    int last=0;
    bool flag=false;
    for(int i=len; i>0; i--)    //从最高位开始枚举
    {
        ans+=dp[i-1][2]*a[i];
        if(flag)ans+=dp[i-1][0]*a[i];   //如果前面出现过49
        if(!flag&&a[i]>4)ans+=dp[i-1][1];   //+[i-1]位数最高位为9并且不包含49的情况
        if(last==4&&a[i]==9)    //如果出现了49
            flag=true;
        last=a[i];
    }
    printf("%I64d\n",ans);
}
int main()
{
    int T;
    init();
    scanf("%d",&T);
    while(T--)
    {
        LL n;
        scanf("%I64d",&n);
        solve(n+1); //n+1可以避免数字末尾是49的时候出错
    }
    return 0;
}