HDU 3652(数位DP)

时间：2022-01-12 12:27:06

题目链接：B-number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4911    Accepted Submission(s): 2816

Problem Description
A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string "13" and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.
Input
Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).
Output
Print each answer in a single line.
Sample Input
13
100
200
1000
Sample Output
1
1
2
2
Author
wqb0039

今天艾教讲了数位DP,自己硬着头皮写，竟然AC了，开心。

数位DP，dp[i][k]这两维是当前枚举到i,k是与给定的数比较，如果前i个数，正好等于给定的数，那么就是k就是1，否则就是0.举个栗子，比如给的最大的是236789.现在枚举到第三位6，如果前两个数是23，那么k=1,否则等于0.   然后对于本题还需两维，一维表示余数0-12，一维表示前面是否有13   d==2?(2):((d==1&&p==3)?2:((d==0&&p==1)?1:0) d =2表示前面已经有13了，d=1表示前面只有1,0表示其他。

初始化dp[0][0][1][0] = 1，对于这个，晚上我和翔哥讨论了一下午，为什么初始化这个dp[0][0][1][0]，或者为什么初始化1.最后对所有dp[n]的数求和，比如给的数是1300，那么求和后得到是1301，数位dp把1300分成了许多集合，满足这个条件的在一个集合，满足那个条件的在那个集合。为什么多一，翔哥自己迷迷糊糊的在分析，我也听的迷迷糊糊，如果有大神路过，希望留下解释，谢谢！

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int mod = ;

int dp[][][][];

char s[];

int mi[];

int cal(int x,int wei,int p)

{

    return x*mi[wei]%p;

}

int main()

{

    mi[]=;

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

        mi[i]=mi[i-]*%;

    while(scanf("%s",s)!=EOF)

    {

        int n = strlen(s);

        memset(dp,,sizeof(dp));

        dp[][][][] = ;

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

        {

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

            {

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

                {

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

                   {

                       if(dp[i][j][k][d]!=)

                       {

                           int l = ;

                           int r = (k==)?s[i]-'':;

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

                           {

                               dp[i+][(j+cal(p,n-i-,))%][(k==&&p==r)?:][d==?():((d==&&p==)?:(((d==||d==)&&p==)?:))]

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

                           /*    if((i+1==4&&(j+cal(p,n-i-1,13))%13==0&&((k==1&&p==r)?1:0)==1&&(d==2?(2):((d==1&&p==3)?2:((d==0&&p==1)?1:0)))==2)||(i+1==4 && (j+cal(p,n-i-1,13))%13==0 && ((k==1&&p==r)?1:0==0) &&(d==2?(2):((d==1&&p==3)?2:((d==0&&p==1)?1:0)))==2))

                               printf("dp[%d][%d][%d][%d] = %d\n",i+1,(j+cal(p,n-i-1,13))%13,(k==1&&p==r)?1:0,d==2?(2):((d==1&&p==3)?2:((d==0&&p==1)?1:0)),dp[i+1][(j+cal(p,n-i-1,13))%13][(k==1&&p==r)?1:0][d==2?(2):((d==1&&p==3)?2:((d==0&&p==1)?1:0))]);*/

                           //     printf("%d dp[%d][%d][%d][%d] = %d    dp[%d][%d][%d][%d] = %d\n", p,i,j,k,d,dp[i][j][k][d],i+1,(j+cal(p,n-i-1,13))%13,(k==1&&p==r)?1:0,d==2?(2):((d==1&&p==3)?2:((d==0&&p==1)?1:0)),dp[i+1][(j+cal(p,n-i-1,13))%13][(k==1&&p==r)?1:0][d==2?(2):((d==1&&p==3)?2:((d==0&&p==1)?1:0))]);//*/

                           }

                       }

                   }

                }

            }

        }

     /*   int ans = 0;

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

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

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

                    ans+=dp[n][i][j][k];*/

        printf("%d\n",dp[n][][][]+dp[n][][][]);

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

    }

    return ;

}

相关文章