HDU2089-不要62

不要62

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

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

80

 

思路:这是均等志数各项DP的入门题目。先附上ppt的下载链接,讲得够呛不利的。链接:点击打开链接

先是是初始化dp数组。dp数组保存的哪怕是盖  j  为初步的  i 
位数字符合要求的数字来小只。

void init()
{
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;//看题目要求,一般状态下以0为开头的0位数状态为1
    for(int i=1;i<=7;i++)//一共最大是7位数
    {
        for(int j=0;j<=9;j++)//从右往左,先模拟第 i 位的取值
        {
            for(int k=0;k<=9;k++)//再摸拟第  i-1 位的取值
            {
                if(j!=4&&!(j==6&&k==2))//判断是否符合条件描述
                {
                    dp[i][j]+=dp[i-1][k];//如果满足条件相当于第 i 位(取值为j)共 i 位数的状态上加上第 i-1 位(取值为k)共 i-1 位的状态
                }
            }
        }
    }
}

然后计算出来digit数组的值,把数倒序保存在屡组被

int cntlen(int n)
{
    int len=0;
    while(n)
    {
        len++;
        n/=10;
    }
    return len;
}
void cal(int n, int len)
{
    memset(digit,0,sizeof(digit));
    for(int i=1;i<=len;i++)
    {
        digit[i]=n%10;
        n/=10;
    }
}

终极是怎么缓解问题的函数

int slove(int n)//其实计算的是【0,n-1】的状态数,这一点PPT中讲到过。对于一个小于n的数,肯定是从高位到低位出现某一位<n的那一位。
{
    int sum=0;//最终的状态数之和
    int len=cntlen(n);
    cal(n,len);
    //这一部分很关键
   for(int i=len;i>=1;i--)//因为数组是倒序保存的,相当于从原来数的个位开始,直到最高位
    {
        for(int j=0;j<digit[i];j++)//这里的 j 模拟的是当前位置的取值,肯定不能等于digit[i]。
                                   //因也是因为ppt中讲过的性质:对于一个小于n的数,肯定是从高位到低位出现某一位<n的那一位。
        {
            if(!(digit[i+1]==6&&j==2)&&j!=4)
            {
                sum+=dp[i][j];//符合条件的累加到sum中
            }
        }
        //下面这个if的位置千万不能放在前面,原因我在下面说
       if(digit[i]==4||(digit[i+1]==6&&digit[i]==2))//当遇到当前位是4或是当前位是2并且下一位是6,就没有必要再进行下去。
                                                     //因为往下走,前面遍历过的位置是不会变的,已经出现了62或者4,后面无论怎么变化都是不合规定的。
        {
            break;
        }
    }
    return sum;
}

先是:为什么上面代码中之 j 取值必须低于digit[i]?

盖起发挥的性质,我们明白相同段落距离内符合要求的累是匪见面等它本身的。

比喻:给有一个数字:123624

首先最高位1的取值,它可以取0。然后起盘算他的状态。他的不过大值是0,然后要后面位置都太要命可以取9,得到的数字就是是099999。这个数字是仅次于100000底。

接下来跳到下一样各2底下,最高位稳定为1非换,就不再要考虑。接着又考虑下一致位。

实际上可以把数字进行拆分:123624=100000+20000+3000+600+20+4

100000底内计算的是【100000,199999】区间的状态

20000底内计算的凡  【10000,19999】区间的状态

3000之内计算的凡    【1000,2999】区间的状态

600之内计算的是      【100,599】区间的状态

20的内计算的是        【10,19】区间的状态

4的内计算的凡          【0,3】区间的状态

前面每一样员少之且见面在生一致位上上,但是最终4没进展增补。合并整个区间就落的是【0,123623】的状态。

第二:为什么www.88bifa.comif必须放在后面不居眼前?

为 j 的取值是自愧不如当前号digit[i]的。

要么地方的例子,123624,倒序放置于屡次组中尽管成了426321。

准程序于最低位4开始,取值0~3。这个是官的。但一旦拿if放在面前,这一部分底状态就没增长去,最终结出就会见变换多少。

当遇当前各类是4或当前各项是2连还下一样各类是6,就从来不必要再进行下去。因为于生移动,前面遍历过的岗位是匪会见转移的,后面无论怎么变化还是不合规定的。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
int dp[8][10];
int digit[10];
void init()
{
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<=7;i++)
    {
        for(int j=0;j<=9;j++)
        {
            for(int k=0;k<=9;k++)
            {
                if(j!=4&&!(j==6&&k==2))
                {
                    dp[i][j]+=dp[i-1][k];
                }
            }
        }
    }
}
int cntlen(int n)
{
    int len=0;
    while(n)
    {
        len++;
        n/=10;
    }
    return len;
}
void cal(int n, int len)
{
    memset(digit,0,sizeof(digit));
    for(int i=1;i<=len;i++)
    {
        digit[i]=n%10;
        n/=10;
    }
}
int slove(int n)
{
    int sum=0;
    int len=cntlen(n);
    cal(n,len);
    for(int i=len;i>=1;i--)
    {
        for(int j=0;j<digit[i];j++)
        {
            if(!(digit[i+1]==6&&j==2)&&j!=4)
            {
                sum+=dp[i][j];
            }
        }
        if(digit[i]==4||(digit[i+1]==6&&digit[i]==2))
        {
            break;
        }
    }
    return sum;
}
int main()
{
    int n,m;
    init();
    while(~scanf("%d%d",&n,&m))
    {
        if((n==0)&&(m==0))
        {
            break;
        }
        printf("%d\n",slove(m)-slove(n-1));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注