动态规划晋级——HDU 3555 Bomb[数位DP详解]

//dp[len][0]表示长度为len不含49的数量  
//dp[len][1]表示长度为len不含44但以9开头的数字的数量  
//dp[len][2]表示长度为len含有49的数量  
#include<stdio.h>  
#include<string.h>  
__int64 dp[20][3];  
int num[20];  
int main(){  
    dp[0][0]=1;  
    for(int i=1;i<=20;i++){  
        dp[i][0]=dp[i-1][0]*10-dp[i-1][1];//要减去9开头的数  
        dp[i][1]=dp[i-1][0];//在不含49的数量中加9在开头  
        dp[i][2]=dp[i-1][2]*10+dp[i-1][1];//以前含49、这一位有10种选择+以前只含9这一位可以是4  
    }  
    int t;  
    scanf("%d",&t);  
    while(t--){  
        int len=1,last=0;  
        __int64 ans=0,n=0;  
        scanf("%I64d",&n);  
        memset(num,0,sizeof(num));  
        n++;  
        while(n>0){//用num数组来记录每一位的数字、为下面递推做准备  
            num[len]=n%10;  
            n/=10;  
            len++;  
        }  
        int flag=0;  
        for(int i=len;i>=1;i--){//从高位往低位递推  
            ans+=dp[i-1][2]*num[i];//如果后面含有49、那么这一位可以填1到(num[i]-1)  
            if(flag==1)//如果前一位挨着49  
                ans+=dp[i-1][0]*num[i];//那么加上这个是没问题的  
            if(flag==0&&num[i]>4)//如果前一位没有挨着49、但是这一位比4大  
                ans+=dp[i-1][1];//那么加上开头为9的是正确的、  
            if(last==4&&num[i]==9)//判断当前位和上一位是否能组成49  
                flag=1;  
            last=num[i];//当前位转移为上一位  
        }  
        printf("%I64d\n",ans);  
    }  
    return 0;  
}