题意：
给定一个区间，求区间内除了所有含有4或62的数字的总数
思路：
刚学数位dp，发现这道题，以前居然用暴力过了，完全没想到是dp（瀑布汗...)然后事实上，感觉这题用朴素暴力会更快。。。唔。。。感觉数位dp好多都能强行暴力。。。
好，回到正题：参照刚刚所说的基本思路。预处理f数组，然后统计[0,m] - [0,n)。f[i,j]代表开头是j的i位数中不含"62"或"4"的数有几个。如f[2,6]包含60,61,63,65,66,67,68,69
伪代码：
f[0,0] = 1;
for i = 1 ~ 7for j = 0 ~ 9 //枚举第i位for k = 0 ~ 9 //枚举第i - 1位if j <> 4 and not(j = 6 and k = 2) f[i,j] = f[i - 1,k] + f[i,j];到这里，我们已经求出i位的开头是j的满足条件的数的个数了，接下来只要统计区间即可。
统计区间[0,n]
从高到低枚举哪一位比n小
如n = 4 5 6
那么ans = ans + f[3,0];
ans = ans + f[3,1];
ans = ans + f[3,...];
这里ppt上没有细说，然后我卡了好久，都没想通（果然我的智商远低于ppt作者的预期）因为f[i][j]保存的是开头是j的i位数中不含"62"或"4"的数的个数，举例来说，f[3][2]代表的是200 ~299区间内满足条件的数的个数假如我要求的区间是0~345，那就是区间0 - 099，100 - 199， 200 - 299，0 - 09， 10 - 19， 20 - 29， 30 - 39，1 ， 2 ， 3 ，4这些区间内合法数的个数之和 ，我们看到，实际上有些区间是重叠的，而重叠部分正好补足高位的数，比如0 - 09重叠部分是0 - 04，剩余补到十位上正好是补足了没有计算的40 - 44部分，同样的0 - 099也是同样的道理，并且依次往上补足。不过从这里我们也能看出，我们这个统计的过程并没有考虑到345本身，所以当给定区间是[n,m]时，我们这个过程计算时n([0,n-1]),m+1([0,m])。
下面是代码：
#include <cstdio>
#include <cstring>
using namespace std;int dp[10][10];
int l[100];int main()
{int n,m;memset(dp, 0, sizeof(dp));dp[0][0] = 1;for(int i = 1; i <= 7; i++){for(int j = 0; j <= 9; j++){for(int k = 0; k <= 9; k++)if(j != 4 && !(j == 6 && k == 2))dp[i][j] = dp[i - 1][k] + dp[i][j];}}while(scanf("%d %d", &n, &m), n||m){int len = 0;//n = n - 1;while(n){len++;l[len] = n % 10;n = n / 10;}l[len + 1] = 0;int ansn = 0;for(int i = len; i; i --){for(int j = 0; j < l[i]; j++){if(j != 4 && (!(j == 2 && l[i + 1] == 6))){ansn = ansn + dp[i][j];// printf("(%d %d) %d\n", i, j, dp[i][j]);}}if(l[i] == 4 || (l[i] == 2 && l[i + 1] == 6))break;}len = 0;m = m + 1;while(m){len++;l[len] = m % 10;m = m / 10;}l[len + 1] = 0;int ansm = 0;for(int i = len; i; i--){for(int j = 0; j < l[i]; j++){if(j != 4 && (!(j == 2 && l[i + 1] == 6))){// printf("(%d %d) %d\n", i, j, dp[i][j]);ansm = ansm + dp[i][j];}}if(l[i] == 4 || (l[i] == 2 && l[i + 1] == 6))break;}
// for(int i = 1; i <= 3; i++)
// for(int j = 0; j <= 9; j++)
// printf("(%d %d) %d\n", i, j, dp[i][j]);printf("%d\n", ansm - ansn);}return 0;
}