不要62

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

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

数位dp入门：

dp[i][j]表示从右往左数第i位上以j开头的符合要求的数有多少个

dp[i][j]是对dp[i-1][k]的累加，满进

举例说明：

3253
dp[4][0] 0000-0999
dp[4][1] 1000-1999
dp[4][2] 2000-2999 3000

dp[3][0] 0000-0099
dp[3][1] 0100-0199 200

dp[2][0] 0000-0009
dp[2][1] 0010-0019
dp[2][2] 0020-0029
dp[2][3] 0030-0039
dp[2][4] 0040-0049 50

dp[1][0] 0
dp[1][1] 1
dp[1][2] 2 3一共表示0-3252这3253个数中符合要求的数有多少个

2403
dp[4][0] 0000-0999
dp[4][1] 1000-1999

dp[3][0] 0000-0099
dp[3][1] 0100-0199
dp[3][2] 0200-0299
dp[3][3] 0300-0399
break;遇到本位是4则后面的位数都不用算了

2623
dp[4][0] 0000-0999
dp[4][1] 1000-1999 2000

dp[3][0] 0000-0099
dp[3][1] 0100-0199
dp[3][2] 0200-0299
dp[3][3] 0300-0399
dp[3][4] 0400-0499
dp[3][5] 0500-0599 600

dp[2][0] 0000-0009
dp[2][1] 0010-0019 20
break;遇到本位是2，上一位是6的后面的位数也不用算了

2003
dp[4][0] 0000-0999
dp[4][1] 1000-1999 2000

dp[1][0] 0
dp[1][1] 1
dp[1][2] 2 3遇到本位是0的直接跳过，没有满进到1就用不了dp[3][0]和dp[2][0]

#include<cstring>

#include<algorithm>

#include<stdio.h>

#include<iostream>

#define ll long long

#define inf 0x3f3f3f3f

using namespace std;

int dp[][];

int a[];

void init()

{

    memset(dp,,sizeof(dp));

    dp[][]=;

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

    {

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

        {

            if(j==) continue;

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

            {

                if(j== && k==) continue;

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

            }

        }

    }/*打印dp表看看啥情况

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

    {

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

        {

            printf("%10d",dp[i][j]);

        }

        printf("\n");

    }*/

}

int slove(int x)

{

    int cnt=;

    int temp=x;

    while(x)

    {

        x=x/;

        cnt++;

    }

    x=temp;

    memset(a,,sizeof(a));///a数组从下标1到cnt顺序存储各个位上的数字，人性化

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

    {

        a[i]=x%;

        x=x/;

    }

    int sum=;for(int i=;i<=cnt;i++)///数组下标从小到大

    {

        int c=a[i];

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

        {

            if(a[i-]== && j==) continue;

            sum+=dp[ cnt+-i ][j];

        }

        if(c== || (c== && a[i-]==) )

            break;

    }

    return sum;

}

int main()

{

    init();

    int n,m;

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

    {

        int ans=slove(m+)-slove(n);

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

    }

    return ;

}

不要6

hdu2089-不要62-（数位dp）

不要62