题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3555
题目大意：
给一个数字n,范围在1~2^63-1，求1~n之间含有49的数字有多少个。
思路：
经典的数位DP，学习了一下，看的别人的代码：http://www.cnblogs.com/luyi0619/archive/2011/04/29/2033117.html
状态转移：
dp[i][0]代表长度为 i 并且不含有49的数字的个数；
dp[i][1]代表长度为 i 并且不含有49，但是最高位是9的数字的个数；
dp[i][2]代表长度为 i 并且含有49的数字的个数。
数组 a[i] 从低位到高位存储 n 的每一位数字。
则：dp[i][0] = dp[i-1][0] * a[i] - dp[i-1][1]; 表示长度为 i 的不含有49的数字的个数等于长度为 i - 1 的不含有49的数字的个数*当前的数字，因为这个位置可以填0~a[i] - 1，然后再减去长度为 i - 1 的最高位是9的数字的个数，因为如果长度为 i - 1 的最高位是9的话，那么高一位就不能填4了，否则就组成了49。
dp[i][1] = dp[i-1][0]; 表示长度为 i 的并且不含有49同时最高位是9的数字的个数等于，长度为 i - 1 的不含有49的数字的个数，因为只要在它的高一位加上一个9就可以了。
dp[i][2] = dp[i-1][2] * a[i] + dp[i-1][1]; 表示长度为 i 的含有49的数字的个数等于，长度为 i - 1 的数字的个数*当前的数字，再加上长度为 i - 1 的并且不含有49同时最高位是9的数字的个数，因为这个时候，只要在高一位加上一个4就可以了，这样在最高的两位就组成了一个49。
做法是从数字的高位向低位扫描，对于第 i 位，
- 首先加上长度为 i - 1 的符合条件的数字个数；
- 再讨论以前是不是出现过49，如果出现过，就要再追加上长度为 i - 1 的不符合条件的数字的个数，因为以前已经有49了；
- 如果没有出现过，就要判断这一位是不是大于4呢，如果大于4，就要再追加上长度为 i - 1 的不含有49但是最高位是9的数字的个数，因为这个时候可以再这一位填4，因为它大于4嘛~；
- 然后就是判断一下，当前位和上一位是不是满足49，如果满足，标记出现了49了！为以后的判断做准备。
其实这个题目还有一个地方不懂，就是为什么要在输入 n 后，要把 n 加1。想了一下特例，比如输入49，按照上面的做法，在第3步，并不会把符合条件的数字加上，因为4不是严格大于4，最后的执行结果就是0，但是如果加上1之后，n就变成了50，这样第3步恰好可以执行，结果就是正确的了。但是对于一般的情况，还是不知道为什么要把n加1……o(╯□╰)o
这题还是卡了很久，照着别人的代码敲的，死活过不了，然后又找了一份代码：http://blog.csdn.net/acm_cxlove/article/details/7819907 才发现输入输出要用%I64d，这不是坑么……原来hdu要用%I64d，囧……
所以，有时候的bug不是算法或者代码有错误，看看你的输入输出吧！还有，类似的情况，比如，输入文件写错了……更悲剧了。。
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cctype>
6 #include <stack>
7 #include <queue>
8 #include <cmath>
9 #include <algorithm>
10 #define lson l, m, rt<<1
11 #define rson m+1, r, rt<<1|1
12 using namespace std;
13 typedef long long int LL;
14 const int MAXN = 0x3f3f3f3f;
15 const int MIN = -0x3f3f3f3f;
16 const double eps = 1e-9;
17 const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
18 {1,1},{1,-1},{-1,-1}};
19 LL dp[21][3]; unsigned long long int n; int a[25];
20 int main(void){
21 #ifndef ONLINE_JUDGE
22 freopen("hdu3555.in", "r", stdin);
23 #endif
24 int t; scanf("%d", &t);
25 memset(dp, 0, sizeof(dp));
26 dp[0][0] = 1;
27 for (int i = 1; i < 21; ++i){
28 dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1];
29 dp[i][1] = dp[i-1][0];
30 dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1];
31 }
32 while (t--){
33 //cin >> n;
34 scanf("%I64d", &n);
35 int len = 0; memset(a, 0, sizeof(a));
36 n++;
37 while (n){
38 a[++len] = n % 10; n /= 10;
39 } LL ans = 0; int last = 0; bool flag = false;
40 for (int i = len; i >= 1; --i){
41 ans += (dp[i-1][2] * a[i]);
42 if (flag) ans += dp[i-1][0] * a[i];
43 if (!flag && a[i] > 4) {ans += dp[i-1][1];}
44 if (last == 4 && a[i] == 9) {flag = true;}
45 last = a[i];
46 }
47 //cout << ans << endl;
48 printf("%I64d\n", ans);
49 }
50
51 return 0;
52 }
就为了输入输出，纠结好久……所以有的时候还是用cin，cout当输入量不大的时候……
还是不懂为什么要把 n 加 1，继续想想，，神牛路过明白的解释一下撒~感激不尽……
貌似有点儿想明白了……也许加 1 的目的就是处理 n 末两位是49的这种特殊情况，如果最后两位不是49，也不影响结果。比如，如果n是149，变成150，结果是1+1 = 2；如果n是123,变成124，结果依然是1；可是，如果要找的是65这种的呢？需要加5么？如果要统计的是一个三位数呢？比如找1~n里面含有123的数字的个数……该怎么做……
做了后面几道题目，明白了为什么要n++，因为后面的for循环求的是(0,n)的开区间的符合条件的数字的数目，题目要求[1,n]这个区间内的符合条件的数字的数目，所以要把区间的右端点加1。这样的处理方式比较方便，就不用判断这个端点是不是如何条件的数字了。膜拜神牛的想法……
标签：数字,49,个数,长度,include,dp,数位 From： https://www.cnblogs.com/YJH6994/p/18118682