送分了QAQ----数位DP

水深无声 2022-10-29 14:21 93阅读 0赞

## 题目描述 ##

题目来源：牛客网  
杭州人称傻乎乎的人为62，而嘟嘟家这里没有这样的习俗。  
相比62，他那里的人更加讨厌数字38，当然啦，还有4这个  
数字！所以啊，嘟嘟不点都不想见到包含38或者4的数字。  
每次给出一个区间\[n，m\],你能找到所有令人讨厌的数字吗？  
***输入描述:***  
多组输入输出；  
输入的都是整数对n、m（0<n≤m<1000000），  
如果遇到都是0的整数对，则输入结束。  
***输出描述:***  
对于每次的输入  
输出全部令人讨厌的数的个数  
示例1  
输入  
1 100  
0 0  
输出  
20

## 笔者思路 ##

这道题是我刚学数位DP所写的第一道题，总的来说就是一道模板题。那么这道题怎么写呢？  
数位DP顾名思义就是按数的位去DP，就是当前位的状态下有多少个满足的数。  
我们假设一个数组dp\[pos\]\[st\],pos代表的是目前数的位置是在第几位（从左往右数），st代表的是三个不同的状态。  
st=0的状态表示的是目前的位和前面的位都不含38和4.  
st=1的状态表示的是前面的位都没出现过38和4，当前位为3.  
st=2的状态表示的是当前位和之前的位有出现过4或38.  
**st=0对应的转移方程：**  
容易得到dp\[pos\]\[0\]=9*dp\[pos-1\]\[0\]-dp\[pos-1\]\[1\]，因为当前既没有38也没有4的位可以根据乘法原理得到dp\[pos-1\]\[0\]9（不是10是因为不能包含4，所以只剩下九个数），为什么要减去dp\[pos-1\]\[1\]呢？因为出现了一种特殊情况，假如pos-1位为3，那么pos位就不可以为8，所以要把dp\[pos-1\]\[1\]减去掉一个，也就是38对应的情况。  
**st=1对应的转移方程**  
易知：dp\[pos\]\[1\]=dp\[pos-1\]\[0\];  
即只能由既没有出现过38也没有出现过4的st==0的上一位状态转移过来。  
**st=2对应的转移方程**  
dp\[pos\]\[2\]=2dp\[pos-1\]\[1\]+dp\[pos-1\]\[0\]+10*dp\[pos-1\]\[2\];  
即对应的st=1的上一状态，我们只需要让目前位为8即可出现38，让目前位为4则出现4，所以上一状态为当前状态提供了2*dp\[pos-1\]\[1\].  
对应st=0的上一状态，我们只需要让目前位为4即可出现4，所以为目前状态提供了dp\[pos-1\]\[0\];  
对应st=2的状态，因为前面出现了4或者38，所以目前位可取任何数，由乘法原理可知为目前状态提供了10*dp\[pos-1\]\[2\].

这里我们采用深搜+记忆化来实现，f数组对应实现记忆化功能，a数组是讲当前给的数一 一拆出来，flag是用来判别下一位是否可以任选。  
那么什么样的位可以导致下一位可以任选呢？比如当前原本拆出来的数对应的位是5，如果当前位取为x,如果x<5那么下一位可以任选，如果==5那么下一位的选择就有限制了。

**代码如下：**

#include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstdio>
    #include<string>
    #include<cstring>
    #include<vector>
    #include<queue>
    #include<stack>
    using namespace std;
    #define ll long long
    int read()
    {
        
        int ans=0,sign=1;
        char ch=getchar();
        while(ch<'0'||ch>'9')
        {
        
            if(ch=='-')
                sign=-1;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
        {
        
            ans=(ans<<1)+(ans<<3)+(ch^48);
            ch=getchar();
        }
        return ans*sign;
    }
    int f[10][3];
    int a[10];
    int dp(int pos,int st,bool flag)
    {
        
        if(pos==0)
            return st==2;
        if(flag&&f[pos][st]!=-1)
            return f[pos][st];
        int x=flag?9:a[pos];
        int ans=0;
        for(int i=0; i<=x; i++)
        {
        
            if(i==4||st==2||(st==1&&i==8))
                ans+=dp(pos-1,2,flag||(i<x));
            else if(i==3)
            {
        
                ans+=dp(pos-1,1,flag||(i<x));
            }
            else
            {
        
                ans+=dp(pos-1,0,flag||(i<x));
            }
        }
        if(flag)
            f[pos][st]=ans;
        return ans;
    }
    int cal(int x)
    {
        
        int cur=0;
        while(x)
        {
        
            a[++cur]=x%10;
            x/=10;
        }
        memset(f,-1,sizeof(f));
        f[0][0]=1;
        return dp(cur,0,0);
    }
    int main()
    {
        
        while(1)
        {
        
            int n=read(),m=read();
            if(n==m&&!n)
                break;
            int ans=cal(m);
            ans-=cal(n-1);
            cout<<ans<<'\n';
        }
        return 0;
    }