HDU 3555 Bomb

最近在練數位dp，這題還是wang了一發，這題是基本題，沒什麼好說的，附上代碼。

#include<stdio.h>
#include<string.h>
#define LL unsigned long long
LL dp[3][30];
LL a[30];
void init()
{
    int i,j,k;
    dp[0][0]=1;
    for(i=1;i<22;i++)
    {
        dp[0][i]=dp[0][i-1]*10-dp[1][i-1];
        dp[1][i]=dp[0][i-1];
        dp[2][i]=dp[2][i-1]*10+dp[1][i-1];
    }
}
LL solve(LL n)
{
    int i,j,k,len;
    for(i=1;n;i++)
    {
        a[i]=n%10;
        n/=10;
    }
    len=i;
    a[len]=0;
    LL ans=0,flag=0;
    for(i=len-1;i>0;i--)
    {
        ans+=a[i]*dp[2][i-1];
        if(flag)ans+=a[i]*dp[0][i-1];
        else
        {
            if(a[i]>4)ans+=dp[1][i-1];//這裡剛開始寫成if(a[i+1]>4)ans+=dp[0][i-1]，錯了一次~
        }
        if(a[i+1]==4&&a[i]==9)flag=1;
    }
    return ans;
}
int main()
{
    init();
    int i,j,k,t;
    LL n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%I64u",&n);
        printf("%I64u\n",solve(n+1));
    }
    return 0;
}