HDU 3555 Bomb (數位DP)

做的第一道數位DP啊！開始在找規律，搜尋，做了很久終于找到了規律，上網一查發現原來這樣的叫數位DP。。

找到的規律就是這個樣子了。有了規律就很好做了。dp[i][0]=dp[i-1][0]*10-dp[i-1][1];是因為要減去49XXX的情況。

//Time:15MS	
//Memory:488K
#include<string.h>
#include<stdio.h>
long long dp[20][3];
int num[20];
int main()
{
    memset(dp,0,sizeof(dp));
    dp[0][0] = 1;
    for(int i = 1;i<= 20;i++){
        dp[i][0]=dp[i-1][0]*10-dp[i-1][1]; //dp[i][0] 表示i位數字中不含49的數字的個數
        dp[i][1]=dp[i-1][0];               //dp[i][1] 表示i位數字中以9開頭的數字的個數
        dp[i][2]=dp[i-1][2]*10+dp[i-1][1];//dp[i][2] 表示i位數字中含有49的數字的個數
    }
    int t;
    scanf("%d",&t);
    while(t--)
	{
        int len = 0,last = 0;
        long long ans = 0;
        long long n = 0;
        scanf("%I64d",&n);
        n++;
        memset(num,0,sizeof(num));
        while(n){
            num[++len]=n%10;
            n/=10;
        }
        bool flag=false;
        for(int i=len;i>=1;i--)
		{
            ans+=dp[i-1][2]*num[i];
            if(flag)
			{
                ans+=dp[i-1][0]*num[i];
            }
            if(!flag && num[i]>4)
			{
                ans+=dp[i-1][1];
            }
            if(last==4 && num[i]==9)
			{
                flag=true;
            }
            last=num[i];
        }
        printf("%I64d\n",ans);
    }
}