HDU 3652 B-number（数位dp）

题意：B数的定义是有字符串“13”且能被整数13整除的数，求[1,n]内的B数个数。

题解：这是数位DP，我也就是刚入门，前两天看到了非递归写法，好麻烦。所以我建议写dfs的方法，容易理解，代码还简短。

在这说一下整除13的事，比如1523这个数，你把它用手自己模拟一遍，发现是15先%13==2，之后是（2*10+2）%13==9 ……，以此类推，最后mod==0&&ok==1，才返回1，（ok标记的是是否出现过“13”）。

AC代码：

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int INF=0x3f3f3f3f;

typedef long long ll;

typedef unsigned long long ull;

#define prN printf("\n")

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d%d",&(N),&(M))

#define SIII(N,M,K) scanf("%d%d%d",&(N),&(M),&(K))

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

const int MAX_N= + ;

const double eps= 1e- ;

int n,dp[][][][],digit[];

int dfs(int pos,int pre,int mod,bool limit,bool ok)

{

    //结束判断

    if (pos==) return ok&&mod==;

    //记忆化判断

    if (dp[pos][pre][mod][ok]!=-&&!limit) return dp[pos][pre][mod][ok];

    int top=limit?digit[pos]:;

    int cnt=;

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

    {

        if (i==&&pre==) cnt+=dfs(pos-,i,(mod*+i)%,limit&&i==top,);

        else cnt+=dfs(pos-,i,(mod*+i)%,limit&&i==top,ok);

    }

    if (!limit) dp[pos][pre][mod][ok]=cnt;

    return cnt;

}

int main()

{

    while(~SI(n))

    {

        cle(dp,-);

        int len=;

        while(n)

        {

            digit[++len]=n%;

            n/=;

        }

        printf("%d\n",dfs(len,,,,));

    }

    return ;

}

秒客网

HDU 3652 B-number（数位dp）

相关文章