数位DP HDU3652

B-number

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

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

Source

2010 Asia Regional Chengdu Site —— Online Contest

题意：
计算N以内的数中含有13并且能被13整除的数的个数

代码：

 1 /*
 2 记忆化搜索+数位DP,不是很理解这一套路，dp[i][j][k],i表示位数，j表示余数，k=0表示没有13，k=1表示末尾是1，
 3 k=2表示有13.一个数除以13可以是前几位除以13的余数连上后几位再除以13......
 4 */
 5 #include<iostream>
 6 #include<string>
 7 #include<cstdio>
 8 #include<cmath>
 9 #include<cstring>
10 #include<algorithm>
11 #include<vector>
12 #include<iomanip>
13 #include<queue>
14 #include<stack>
15 using namespace std;
16 int n;
17 int dp[13][13][3];  
18 int c[13];
19 int dfs(int lne,int mod,int have,int lim)  //lim代表是否为上限
20 {
21     if(lne<=0)    //没有位数了返回符合的情况
22     return mod==0&have==2;
23     if(!lim&&dp[lne][mod][have]!=-1)  //没有上限并且已被访问过
24     return dp[lne][mod][have];
25     int num=lim?c[lne]:9; //假设该位是2，下一位是3，如果现在算到该位为1，那么下一位是能取到9的，
26                            //如果该位为2，下一位只能取到3  
27     int ans=0;
28     for(int i=0;i<=num;i++)
29     {
30         int nmod=(mod*10+i)%13;  //看是否能整除13，而且由于是从原来数字最高位开始算，
31                                   //事实上这个过程就是一个除法过程  
32         int nhave=have;
33         if(have==0&&i==1) nhave=1;  //末尾不是1，现在加入的是1 
34         if(have==1&&i!=1&&i!=3) nhave=0;   //末尾是1，现在加入的不是1
35         if(have==1&&i==3) nhave=2;   //末尾是1，现在加入的是3  
36         ans+=dfs(lne-1,nmod,nhave,lim&&i==num);  //lim&&i==num，在最开始，取出的num是最高位，
37     //所以如果i比num小，那么i的下一位都可以到达9，而i==num了，最大能到达的就只有,c[len-1]  
38     }
39     if(!lim)
40     dp[lne][mod][have]=ans;  //dp只记录没有限的值
41     return ans;
42 }
43 int main()
44 {
45     while(scanf("%d",&n)!=EOF)
46     {
47         memset(dp,-1,sizeof(dp));
48         int cnt=0;
49         while(n)
50         {
51             c[++cnt]=n%10;
52             n/=10;
53         }
54         printf("%d
",dfs(cnt,0,0,1));
55     }
56     return 0;
57 }