hdu 2089 不要62 (数位dp基础题)

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

不要62

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 58665 Accepted Submission(s): 23095

Problem Description

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input

输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。

Output

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

Sample Input

1 100
0 0

Sample Output

题目大意：

求n..m区间里不含4和连续的62的数的个数。

区间dp基础题。

以下摘自xiaoxia、的cnblog，略有删改：

dp[i][j] 表示i位数，首位是j的数字有多少符合要求的。

很容易得到递推公式：

如j=4时：dp[i][j]=0

j!=4时：

如何根据数组dp求对于一个数n，0~n满足要求的数呢？

对于一个数,例如335，对应dp[3][3],但是满足要求的数有336,347,358……这些数超过了335……

所以通过dp[3][0],dp[3][1],dp[3][2]求得首位数字小于3的满足条件的三位数，dp[3][0]求得的数是001,052,093...也就是所有满足条件的一位或两位数……我们求得所有的2xx,1xx,0xx.

接下来要求的是如334,327这类首位是3满足条件的数字，既然首位只能是3，也就是第一位已经选完了，那么我们只要选择满足小于35的数字就可以了。和上面同理，我们只要求出dp[2][0],dp[2][1],dp[2][2]就可以求出首位小于3的两位数。这时求得的是32x,31x,30x。

然后我们求所有小于5的数字就ok。小于5也就是dp[1][0]，dp[1][1]，dp[1][2]，dp[1][3]，dp[1][4]。这时求得的是53x.

到此，所有小于335且满足的数全部求出。

但是还需要考虑的问题是62,4。

如果某一位数字为4，如77432的第三位（从左向右看）是4，那么我们依次求出6xxxx，5xxxx，...，0xxxx，76xxx，75xxx，...，70xxx，773xx，773xx，...，770xx，我们接来下需要求的是7742x....7740x，但这时所求的数是774xx的数，必然含有4，所以这时我们停止。

对于62，如果某一位数字是6，如5675，我们求完5xxx,4xxx,...0xxx之后再求56xx时，注意566x,565x,..,563x,561x,没有562x。如果数字中含有62，如5627，那么同4，求到562x的时候就应该停止继续求下去了。

因为求得的是小于n的数，所以求[0,n]之间的数需要求n+1.看代码更容易理解。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;//最多maxn位数

int dp[maxn+][];//dp[i][j]表示以j开头的i位数满足条件的个数

int d[maxn+];

//记忆化

void init()

{

    memset(dp,,sizeof(dp));

    for(int i=;i<=;i++)

    {

        if(i!=)

            dp[][i]=;

    }

    for(int i=;i<=maxn;i++)

    {

        for(int j=;j<=;j++)

        {

            if(j!=)

            {

                for(int k=;k<=;k++)

                    if(j!=||k!=)

                        dp[i][j]+=dp[i-][k];

            }

        }

    }

}

//1..x-1符合条件的个数

int solve(int x)

{

    int ret=;

    int len=;

    while(x)

    {

        len++;

        d[len]=x%;

        x/=;

    }

    d[len+]=;

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

    {

        for(int j=;j<d[i];j++)

            if(d[i+]!=||j!=)

                ret+=dp[i][j];

        if(d[i]==||(d[i+]==&&d[i]==))

            break;

    }

    return ret;

}

int main()

{

    init();

    int n,m;

    while(scanf("%d%d",&n,&m),n)

    {

        printf("%d\n",solve(m+)-solve(n));

    }

    return ;

}