数位\(dp\)搞了一上午才搞懂。靠这种傻\(X\)的东西竟然花了我一上午的时间。

数位\(dp\)

概念

数位\(dp\)就是强制你分类一些数，例如给你一段区间，然后让你求出不包含\(2\)的数的个数。

思想

利用前缀和的思想，然后求出区间端点的前缀和这样作差就可以了。

实现方式

有两种实现方式。

记忆化搜索版

这种方法比较好理解（例题不要\(37\)）

int dfs(int pos,int pre,int sta,bool limit) {

    if (pos==-1) return 1;

    if (!limit && dp[pos][sta]!=-1) return dp[pos][sta];

    int u = limit?a[pos]:9;

    int cnt = 0;

    for (int i=0; i<=u; ++i) {

        if (i==4 || (pre==3&&i==7)) continue;

        cnt += dfs(pos-1,i,i==3,limit&&i==a[pos]);

    }

    if (!limit) dp[pos][sta] = cnt;

    return cnt;

}

查询区间\([0 \ldots n]\)

动态规划版

（例题不要\(62\)）

void get_dp()

{

    dp[0][0]=1;

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

    {

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

        {

            if (j==4) dp[i][j]=0;

            else if (j==6)

            {

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

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

                dp[i][j]-=dp[i-1][2];

            }

            else

            {

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

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

            }

        }

    }

}

查询区间\([0\ldots n)\)

完整代码

动态规划

#include<cstdio>

const int maxn=10;

long long dp[maxn][10];

void get_dp()

{

    dp[0][0]=1;

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

    {

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

        {

            if (j==4) dp[i][j]=0;

            else if (j==6)

            {

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

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

                dp[i][j]-=dp[i-1][2];

            }

            else

            {

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

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

            }

        }

    }

}

int a[maxn];

long long solve(int n)

{

    a[0]=0;

    while (n)

    {

        a[++a[0]]=n%10;

        n/=10;

    }

    long long ans=0;

    a[a[0]+1]=0;

    for (int i=a[0];i>=1;i--)

    {

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

            if(j!=4 && !(a[i+1]==6 && j==2))

                ans+=dp[i][j];

        if (a[i]==4) break;

        if (a[i+1]==6 && a[i]==2) break;

    }

    return ans;

}

int main()

{

    int n,m;

    get_dp();

    while (scanf("%d %d",&n,&m)==2 && (n||m))

    {

        long long k1=solve(m+1);

        long long k2=solve(n);

        printf("%I64d\n",k1-k2);

    }

    return 0;

}

关于动态规划版有个难点，就是\(solve\)函数里面的两个\(break\)。因为我们枚举的是最高位，所以当我们最高位枚举到不合法数的时候，我们就会固定，那么剩下数的任何数都是不合法的，所以\(break\)

记忆化搜索

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long LL;

int a[20],p;

int dp[20][2];

int dfs(int pos,int pre,bool sta,bool limit) {

    if (pos==-1) return 1;

    if (!limit && dp[pos][sta]!=-1) return dp[pos][sta];

    int u = limit?a[pos]:9;

    int cnt = 0;

    for (int i=0; i<=u; ++i) {

        if (i==4 || (pre==3&&i==7)) continue;

        cnt += dfs(pos-1,i,i==3,limit&&i==a[pos]);

    }

    if (!limit) dp[pos][sta] = cnt;

    return cnt;

}

int work(int x) {

    p = 0;

    while (x) {

        a[p++] = x%10;

        x /= 10;

    }

    return dfs(p-1,-1,0,true);

}

int main() {

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

    int l,r;

    cin>>l>>r;

    printf("%d",work(r)-work(l-1));

    return 0;

}

以上代码借鉴。

巴特西

数位$dp$