hdu3652——B-number（数位dp变形）-白红宇

hdu3652——B-number（数位dp变形）

阅读量：2343 次

发布时间：2019-05-10

本文共 1449 字，大约阅读时间需要 4 分钟。

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

100

200

1000

Sample Output

加了一个还要被13整除的条件，那就在状态数组多加一项表示被13整除的情况，当这项等于0说明能被13整除

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #define INF 0x3f3f3f3f#define MAXN 10000000005#define Mod 10001using namespace std;int dight[30],dp[30][3][13];int dfs(int pos,int s,bool limit,int mod){ if(pos==0) return s==2&&mod==0; if(!limit&&dp[pos][s][mod]!=-1) return dp[pos][s][mod]; int end,ret=0; if(limit) end=dight[pos]; else end=9; for(int d=0;d<=end;++d) { int have=s,nmod=(mod*10+d)%13; if(s==1&&d==3) have=2; if(s==0&&d==1) have=1; if(s==1&&d!=1&&d!=3) have=0; ret+=dfs(pos-1,have,limit&&d==end,nmod); } if(!limit) dp[pos][s][mod]=ret; return ret;}int solve(int a){ memset(dight,0,sizeof(dight)); int cnt=1; while(a!=0) { dight[cnt++]=a%10; a/=10; } return dfs(cnt-1,0,1,0);}int main(){ memset(dp,-1,sizeof(dp)); int n; while(~scanf("%d",&n)) { printf("%d\n",solve(n)); } return 0;}

转载地址：http://uvcvb.baihongyu.com/

你可能感兴趣的文章

进程与线程的区别与联系、进程与线程的通信方式