HDOJ 3555 Bomb (数位DP)

题意：求1-N中有多少个数包含字符串"49"。1 <= N <= 2^63-1

重写这题就是为了学习数位DP的dfs写法，感觉dfs的写法思路更清晰，速度也更快。

#include <stdio.h>
#include <string.h>
#define N 20
typedef __int64 LL;
LL dp[N][3];
int digit[N];
LL dfs(int pos,int s,int f)
{
    if(pos==-1) return s==2;
    if(!f&&dp[pos][s]!=-1)  return dp[pos][s];
    int max=f?digit[pos]:9;
    LL ret=0;
    for(int i=0;i<=max;i++)
    {
        int ns=s;
        if(s==0&&i==4)  ns=1;
        else if(s==1&&i!=4) ns=0;
        if(s==1&&i==9)  ns=2;
        ret+=dfs(pos-1,ns,f&&i==max);
    }
    if(!f)  dp[pos][s]=ret;
    return ret;
}
LL cal(LL x)
{
    int pos=0;
    while(x)
    {
        digit[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,0,1);
}
int main()
{
    int t;
    memset(dp,-1,sizeof(dp));
    scanf("%d",&t);
    while(t--)
    {
        LL x;
        scanf("%I64d",&x);
        printf("%I64d\n",cal(x));
    }
    return 0;
}