当前位置:首页 » C语言&C++

【Hdu3652】B-number(数位DP)

2017-12-22 21:40 本站整理 浏览(13)

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; 
}