Bomb

   Bomb                   

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?

3150500Sample Output
0115
//    pos    = 当前处理的位置(一般从高位到低位)//    status   = 上一个位的数字(更高的那一位)//     pre = 要达到的状态,如果为1则可以认为找到了答案,到时候用来返回,//         　　 给计数器+1。//    last  = 是否受限,也即当前处理这位能否随便取值。如567,当前处理6这位,//         　　 如果前面取的是4,则当前这位可以取0-9。如果前面取的5,那么当前//         　　 这位就不能随便取，不然会超出这个数的范围,所以如果前面取5的//         　　 话此时的limit=1,也就是说当前只可以取0-6。////    用DP数组保存这三个状态是因为后转移的时候会遇到很多重复的情况。
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;int a[20];long long dp[20][2][12];long long dfs(int pos,bool pre,int status,bool last){    int i;    if (pos==-1) return pre;//已结搜到尽头,返回"是否找到了答案"这个状态。
//DP里保存的是完整的,也即不受限的答案,所以如果满足的话,可以直接返回。    if (!last && dp[pos][pre][status]!=-1) return dp[pos][pre][status];    int len=last?a[pos]:9;    long long ans=0;
//last用&&是因为只有前面受限、当前受限才能    //推出下一步也受限，比如567,如果是46X的情况,虽然6已经到尽头,但是后面的    //个位仍然可以随便取,因为百位没受限,所以如果个位要受限,那么前面必须是56。    for (i=0;i<=len;i++)    {        if (status==4 && i==9) ans+=dfs(pos-1,true,i,last && (i==len));        else ans+=dfs(pos-1,pre,i,last && (i==len));    }    if (!last)    {        dp[pos][pre][status]=ans;    }    return ans;}long long Cal(long long t){    int i,j,pos=0;    while(t)    {        a[pos++]=t%10;        t/=10;    }    return dfs(pos-1,0,0,1);}int main(){    int i,j,T;    __int64 n;    scanf("%d",&T);    while(T--)    {        memset(dp,-1,sizeof(dp));        scanf("%I64d",&n);        printf("%I64d/n",Cal(n));    }    return 0;}          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