hdu3555_数位dp

http://acm.hdu.edu.cn/showproblem.php?pid=3555
题意，1-n, 有多少个数含有49
 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cstdio>
 6 #include <vector>
 7 #include <ctime>
 8 #include <queue>
 9 #include <list>
10 #include <set>
11 #include <map>
12 using namespace std;
13 #define INF 0x3f3f3f3f
14 typedef long long LL;
15 
16 LL dp[25][5];
17 // dp[1][0] = 10;//没有49
18 // dp[1][1] = 1;//9
19 // dp[1][2] = 0;//有49
20 void find()
21 {
22     memset(dp, 0, sizeof(dp));
23     dp[0][0] = 1;
24     for(int i = 1; i <= 20; i++)
25     {
26         dp[i][0] = (LL)dp[i - 1][0] * 10 - dp[i - 1][1];
27         dp[i][1] = dp[i - 1][0];
28         dp[i][2] = (LL)dp[i - 1][2] * 10 + dp[i - 1][1];
29     }
30 }
31 
32 void solve(LL n)
33 {
34     int len = 0;
35     int bit[25];
36     while(n)
37     {
38         bit[++len] = n % 10;
39         n /= 10;
40     }
41     bit[len + 1] = 0;
42     LL ans = 0;
43     int flag = 0;
44     for(int i = len; i > 0; i--)
45     {
46         ans += (LL)dp[i - 1][2] * bit[i];
47         if(flag)
48             ans += (LL)dp[i - 1][0] * bit[i];
49         if(!flag && bit[i] > 4)
50             ans += dp[i - 1][1];
51         if(bit[i + 1] == 4 && bit[i] == 9)
52             flag = 1;
53     }
54     printf("%I64d
", ans);
55 }
56 int main()
57 {
58     int t;
59     LL n;
60     scanf("%d", &t);
61     find();
62     while(t--)
63     {
64         scanf("%I64d", &n);
65         solve(n + 1);
66     }
67     return 0;
68 }
View Code