题意：定义一个数如果含有数字4，或者出现“62”则为不吉利数，否则为吉利数。比如242，8262均不吉利， 但22682吉利。求区间[a, b]中有多少个数为吉利数。
0 < a <= b < 10^6。
解法：问题即是求对于任意的x < 10^6，求[0, x)内有多少个吉利数。
设d[i][0]表示长度为i的数(首位为0也算，比如0020长度为4)中，首位不为2且吉利的数的个数。
d[i][1]表示长度为i的数中，首位为2且吉利的数的个数。
d[i][2]表示长度为i的数中，不吉利的数的个数。
首先预处理出d[8][3]。
然后从对x从高位到低位遍历，比如x为23476，遍历到4时，求出所有小于23400的，前缀为23的不吉利数。详见代码。
tag:数位DP, 基础题
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-12-14 13:40 4 * File Name: DP-HDU-2089.cpp 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <algorithm> 10 11 using namespace std; 12 13 #define CLR(x) memset(x, 0, sizeof(x)) 14 15 int s[20], d[10][3]; 16 17 int gao(int x) 18 { 19 int ret = x + 1; 20 CLR (s); 21 int len = 0; 22 while (x){ 23 s[len++] = x % 10; 24 x /= 10; 25 } 26 s[len] = 0; 27 28 bool flag = 0; 29 for (int i = len-1; i >= 0; -- i){ 30 ret -= s[i] * d[i][2]; 31 if (flag) ret -= s[i] * (d[i][0] + d[i][1]); 32 else{ 33 if (s[i] > 6) ret -= d[i][1]; 34 if (s[i] > 4) ret -= d[i][0] + d[i][1]; 35 if (s[i+1] == 6 && s[i] > 2) ret -= d[i][0] + d[i][1]; 36 } 37 38 if ((s[i+1] == 6 && s[i] == 2) || s[i] == 4) flag = 1; 39 } 40 return ret; 41 } 42 43 int main() 44 { 45 CLR (d); 46 d[0][0] = 1; 47 for (int i = 1; i < 10; ++ i){ 48 d[i][0] = 8 * (d[i-1][0] + d[i-1][1]) - d[i-1][1]; 49 d[i][1] = d[i-1][1] + d[i-1][0]; 50 d[i][2] = d[i-1][0] + 2*d[i-1][1] + 10*d[i-1][2]; 51 } 52 53 int n, m; 54 while (scanf ("%d%d", &n, &m) != EOF){ 55 if (!n && !m) break; 56 printf ("%d ", gao(m+1) - gao(n)); 57 } 58 return 0; 59 }