hdu3555 数位dp

给定一个数n，判断1-->n有多少个数字含“49”

可以用dp的方式来解决，

dp[i][0] 表示长度为i，不含"49"的数字的个数

dp[i][1] 表示长度为i，第i位为数字9的个数

dp[i][2] 表示长度为i，含”49“的数字的个数

所以，dp[i][0] 的包含dp[i][1]的

状态转移方程如下：

dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1]; 长度为i不含"49"，可以由长度为i-1不含"49"的数字在第i位补上0->9得到，并减去以9开头，补上4，得到含"49"的数字的个数

dp[i][1] = dp[i-1][0]; 在长度i-1不含"49"的数字的第i为补上9

dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1]; 长度为i含"49"，可以由长度为i-1含"49"的数字在第i位补上0->9得到，并加上以9开头，补上4，得到含"49"的数字的个数

刚开始的时候我注意到一个问题，就是在第i位补0的情况。

就是dp[2][2] = 1(数字49)

dp[3][2] = dp[2][2] * 10 + dp[2][1], 那么dp[3][2]不是把数字049给算在内了吗。

事实上，确实是这样子，而且也是有问题的，看了统计部分的代码才知道怎么回事。

dp完后就要统计小于等于n的数中有多少个数字含“49”

统计区间[1,n],从高到低枚举哪一位比n+1小，比如说n+1=5001;

千位比n小，那么可以取值0-->4 ans += 5 * dp[3][2]; 要知道dp[3][2] 统计了数字"49","149","249","349","449","490","491","492","493","494","495","496","497","498","499", “549","649","749","849","949"

所以当千位取0时，就将这些2位数和3位数给统计进去了。这就是为什么dp[3][2]要统计数字“049”的原因

百位比n小，没有东西比0小， ans += 0 * dp[2][2];

十位比n小，没有东西比0小， ans += 0 * dp[1][2];

个位比n小，那么可以取值1， ans += 1 * dp[0][2];

当然还有一些特殊情况没有讨论，详细见源代码

 1 #include <stdio.h>
 2 #include <string.h>
 3 typedef __int64 LL;
 4 LL dp[22][3];
 5 /*
 6 dp[i][0] 长度为i，不含49的个数     dp[i][0] 包含dp[i][1]
 7 dp[i][1] 长度为i，含前缀9的个数
 8 dp[i][2] 长度为i，含49的个数
 9 */
10 void init()
11 {
12     int i;
13     dp[0][0] = 1;
14     for(i=1; i<=20; ++i)
15     {
16         dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1];//长度为i，不含49的个数，可以由长度为i-1，不含49的数字在第i为添加0-9，
17         dp[i][1] = dp[i-1][0];//在长度为i-1，不含49的数字前面添个9
18         dp[i][2] = dp[i-1][2]*10 + dp[i-1][1];//长度为i，含49的个数，可以在含49的数字前面添加0-9，在9开头的数字前面添加4
19     }
20 }
21 int num[22];
22 int main()
23 {
24     init();
25     printf("%d
",dp[3][2]);
26     int t,i;
27     scanf("%d",&t);
28     while(t--)
29     {
30         LL n;
31         int len = 0;
32         scanf("%I64d",&n);
33         n+=1;
34         while(n)
35         {
36             num[++len] = n % 10;
37             n /= 10;
38         }
39         num[len+1] = 0;
40         LL ans = 0;
41         bool flag = false;
42         for(i=len; i>=1; --i)
43         {
44 
45             ans += num[i] * dp[i-1][2];
46             if(flag)//数字n的前面含有49，
47                 ans += num[i] * dp[i-1][0];//后面的i-1位数字有多少个不含49，那么也可以算含有"49"的数字
48             if(!flag && num[i]>4)//如果第i位的数字大于4，那么第i为取值4的时候
49                 ans += dp[i-1][1];//后面的i-1位数字有多少个是以9开头，那么也可以算含有"49"的数字
50             if(num[i+1]==4 && num[i]==9)
51                 flag = true;
52         }
53         printf("%I64d
",ans);
54 
55     }
56     return 0;
57 }

数位dp参考资料：http://wenku.baidu.com/link?url=zSYj4Dfy46C-l4L-ryGsuhzUE_SY5M6XfniTpfTYbHnHhrvvrmvN7DwG-OonqHvANFbl5SWE_46COUWxTNhuXJ8WRr6YugeJKFdDKIJSK4e