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