[Hdu3652]B-number（数位DP）

Description

题目大意：求小于n是13的倍数且含有'13'的数的个数。

(1 <= n <= 1000000000)

Solution

数位DP，题目需要包含13，且被13整除，所以状态应该多2个，

\(F[i][j][k]\)表示位数为i，余数为j，包含13状态为k的方案数

其中k(0,1,2)，2表示已经包含13，1表示上一个为1，否则为0

记忆化打法

Tips:

1. 数组k维要开到3
2. DP数组只算一次，只需开始初始化一次
3. 计算转移的k时的顺序

Code

#include <cstdio>
#include <cstring>

int n,d[15],f[15][15][3];

int dfs(int p,int mo,int exi,int lim){
    int &tmp=f[p][mo][exi],r=0;
    if(!p) return exi==2&&!mo;
    if(!lim&&tmp!=-1) return tmp;   
    
    int mx=lim?d[p]:9;
    for(int i=0;i<=mx;++i){
        int t=0;
        if(exi==2) t=2;//必须先判，否则错解
        else if(exi==1&&i==3) t=2;
        else if(i==1) t=1;
        r+=dfs(p-1,(mo*10+i)%13,t,lim&&(i==mx));
    }
    return lim?r:tmp=r;
}

int main(){
    memset(f,-1,sizeof(f));
    while(~scanf("%d",&n)){
        int len=0;
        while(n){
            d[++len]=n%10;
            n/=10;
        }
        printf("%d\n",dfs(len,0,0,1));
    }
    return 0; 
}