Bomb

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

3
1
50
500

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;
}