hdu3652 B-number

题意：

求1~n中出现“13”并且能被13整除的数的个数。(1 <= n <= 1000000000).

思路：

数位dp。

实现：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int num[15], n;
 7 
 8 int dp[15][13][10][2];
 9 int dfs(int now, int mod, int last, bool ok, bool flag)
10 {
11     if (now == 0)
12     {
13         return !mod && ok;
14     }
15     if (!flag && dp[now][mod][last][ok] != -1)
16         return dp[now][mod][last][ok];
17     int res = 0;
18     int u = flag ? num[now] : 9;
19     for (int i = 0; i <= u; i++)
20     {
21         bool tmp = false;
22         if (last == 1 && i == 3)
23             tmp = true;
24         res += dfs(now - 1, (mod * 10 + i) % 13, i, ok || tmp, flag && i == u);
25     }
26     return flag ? res : dp[now][mod][last][ok] = res;
27 }
28 
29 int solve(int n)
30 {
31     int sum = 0;
32     while (n)
33     {
34         num[++sum] = n % 10;
35         n /= 10;
36     }
37     return dfs(sum, 0, 0, 0, true);
38 }
39 
40 int main()
41 {
42     while (scanf("%d", &n) != EOF)
43     {
44         memset(dp, -1, sizeof(dp));
45         printf("%d
", solve(n));
46     }
47     return 0;
48 }