【学习笔记&训练记录】数位DP

时间：2022-12-12 22:08:46

数位DP,即对数位进行拆分,利用数位来转移的一种DP,一般采用记忆化搜索,或者是先预处理再进行转移

一个比较大略的思想就是可以对于给定的大数,进行按数位进行固定来转移记录答案

区间类型的,可以考虑前缀和的思想,求[l,r]可以看做求[1,r]-[1,l)

其实还有一种,是按照二进制建一颗0,1树来表示,来做,但是比并没有做过,以后再总结

HDU-2089

题目大意:对于区间[L,R]求有多少不包含'62'且不包含'4'的数,题目允许有前导零

思路:

数位DP,考虑F[i][j]表示位数为i,最高位为j的满足的个数

预处理后,统计答案即可,统计答案大致就是固定每一位,进行统计

CODE:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

int n,m;

int F[][];

void prework()

{

    F[][]=;

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

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

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

                if (j!= && !(j==&&k==))

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

}

int Calc(int x)

{

    int digit[]={},len=,ans=;

    while (x!=) {digit[++len]=x%; x/=;}

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

        {

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

                if (j!= && !(j==&&digit[i+]==))

                    ans+=F[i][j];

            if (digit[i]== || (digit[i]==&&digit[i+]==)) break;

        }

    return ans;

}

int main()

{

    prework();

    n=read(),m=read(); if (n>m) swap(n,m);

    while (n!= && m!=)

        {

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

            n=read(),m=read(); if (n>m) swap(n,m);

        }

    return ;

}

HDU-3652

题目大意:给定n,求到n中,包含'13'且被13整除的数的个数

思路:

设计状态F[i][j][k][0/1]表示位数为i,最高位为j的%13余k的数字包含和不包含13的个数

那么同样预处理,这里不含前导零,需要额外做一个值去进行计算,计算到n以内的,计算n+1即可

CODE:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

long long n;

long long F[][][][];

long long cf(int x,int y)

{

    long long re=x;

    for (int i=; i<y; i++) re*=;

    return re;

}

void prework()

{

    for (int i=; i<=; i++) F[][i][i%][]=;

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

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

            {

                tmp=cf(j,i-);

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

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

                        {

                            F[i][j][(tmp+l)%][]+=F[i-][k][l][];

                            if (j== && k==)

                                F[i][j][(tmp+l)%][]+=F[i-][k][l][];

                            else

                                F[i][j][(tmp+l)%][]+=F[i-][k][l][];

                        }

            }

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

//        for (int j=0; j<=9; j++)

//            for (int k=0; k<13; k++)

//                printf("%I64d %I64d\n",F[i][j][k][1],F[i][j][k][0]);

}

long long Calc(long long x)

{

    int digit[]={},len=,f=; long long ans=;

    while (x) {digit[++len]=x%; x/=;}

    for (int i=; i<=digit[len]-; i++)

        ans+=F[len][i][][];

    long long tmp=cf(digit[len],len-);

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

        {

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

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

                    {

                        if ((tmp+k)%==) ans+=F[i][j][k][];

                        if ((tmp+k)%== && (digit[i+]== && j==))

                            ans+=F[i][j][k][];

                        else if ((tmp+k)%== && f) ans+=F[i][j][k][];

                    }

            if (digit[i]== && digit[i+]==) f=;

            tmp+=cf(digit[i],i-);

        }

    return ans;

}

int main()

{

    prework();

    while (scanf("%lld",&n)!=EOF)

        printf("%lld\n",Calc(n+));

    return ;

}

相关文章