题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3555

3

1

50

500

0

1

15

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.

题意：

求0 到n的数中有多少个数字是含有‘49’的。

PS：

数位DP

//dp[i][j]:长度为i的数的第j种状态

//dp[i][0]:长度为i可是不包括49的方案数

//dp[i][1]:长度为i且不含49可是以9开头的数字的方案数

//dp[i][2]:长度为i且包括49的方案数

(转)状态转移例如以下

dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1];  // not include 49  假设不含49且，在前面能够填上0-9 可是要减去dp[i-1][1] 由于4会和9构成49

dp[i][1] = dp[i-1][0];  // not include 49 but starts with 9  这个直接在不含49的数上填个9即可了

dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1]; // include 49  已经含有49的数能够填0-9，或者9开头的填4



接着就是从高位開始统计



在统计到某一位的时候，加上 dp[i-1][2] * digit[i] 是显然对的。由于这一位能够填 0 - (digit[i]-1)

若这一位之前挨着49，那么加上 dp[i-1][0] * digit[i] 也是显然对的。

若这一位之前没有挨着49，可是digit[i]比4大，那么当这一位填4的时候，就得加上dp[i-1][1]

代码例如以下：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef __int64 LL;

LL dp[27][3];

int c[27];

//dp[i][j]:长度为i的数的第j种状态

//dp[i][0]:长度为i可是不包括49的方案数

//dp[i][1]:长度为i且不含49可是以9开头的数字的方案数

//dp[i][2]:长度为i且包括49的方案数

void init()

{

    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][1] = dp[i-1][0]*1;

        dp[i][2] = dp[i-1][2]*10+dp[i-1][1];

    }

}

int cal(LL n)

{

    int k = 0;

    memset(c,0,sizeof(c));

    while(n)

    {

        c[++k] = n%10;

        n/=10;

    }

    c[k+1] = 0;

    return k;

}

void solve(int len, LL n)

{

    int flag = 0;//标记是否出现过49

    LL ans = 0;

    for(int i = len; i >= 1; i--)

    {

        ans+=c[i]*dp[i-1][2];

        if(flag)

        {

            ans+=c[i]*dp[i-1][0];

        }

        else if(c[i] > 4)

        {

            //这一位前面没有挨着49。但c[i]比4大，那么当这一位填4的时候，要加上dp[i-1][1]

            ans+=dp[i-1][1];

        }

        if(c[i+1]==4 && c[i]==9)

        {

            flag = 1;

        }

    }

    printf("%I64d\n",ans);

}

int main()

{

    int t;

    LL n;

    init();

    scanf("%d",&t);

    while(t--)

    {

        scanf("%I64d",&n);

        int len = cal(n+1);

        solve(len, n);

    }

    return 0;

}

DFS版

代码例如以下：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define LL __int64

LL n, dp[25][3];

//dp[i][j]:长度为i。状态为j

int digit[25];

//nstatus: 0：不含49, 1：不含49但末尾是4, 2 :含49

LL DFS(int pos, int status, int limit)

{

    if(pos <= 0) // 假设到了已经枚举了最后一位。而且在枚举的过程中有49序列出现

        return status==2;//注意是 ==

    if(!limit && dp[pos][status]!=-1)   //对于有限制的询问我们是不可以记忆化的

        return dp[pos][status];

    LL ans = 0;

    int End = limit?digit[pos]:9;   // 确定这一位的上限是多少

    for(int i = 0; i <= End; i++)   // 每一位有这么多的选择

    {

        int nstatus = status;       // 有点else s = statu 的意思

        if(status==0 && i==4)//高位不含49。而且末尾不是4 ，如今末尾添4返回1状态

            nstatus = 1;

        else if(status==1 && i!=4 && i!=9)//高位不含49。且末尾是4，如今末尾加入的不是4返回0状态

            nstatus = 0;

        else if(status==1 && i==9)//高位不含49，且末尾是4，如今末尾加入9返回2状态

            nstatus = 2;

        ans+=DFS(pos-1, nstatus, limit && i==End);

    }

    if(!limit)

        dp[pos][status]=ans;

    return ans;

}

int cal(LL x)

{

    int cnt = 0;

    while(x)

    {

        digit[++cnt] = x%10;

        x/=10;

    }

    digit[cnt+1] = 0;

    return cnt;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        memset(dp,-1,sizeof(dp));

        scanf("%I64d",&n);

        int len = cal(n);

        LL ans = DFS(len, 0, 1);

        printf("%I64d\n",ans);

    }

    return 0;

}