1 100 0 0
80
题解及代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int f[7][10];
void init()
{
memset(f,0,sizeof(f));
f[0][0]=1;
for(int i=1; i<=6; i++)
for(int j=0; j<=9; j++)
for(int k=0; k<=9; k++)
if(!(j==4||j==6&&k==2))
f[i][j]+=f[i-1][k];
}
int solve(int n)
{
if(n==0) return 1;
int k=1,r=n,ans=0;
int digt[8];
memset(digt,0,sizeof(digt));
while(r)
{
digt[k++]=r%10;
r/=10;
}
for(int i=k-1;i>=1;i--)
{
for(int j=0;j<digt[i];j++)
if(!(j==4||j==2&&digt[i+1]==6))
{
ans+=f[i][j];
//cout<<ans<<"i:"<<i<<"j:"<<j<<endl;
}
if(digt[i]==4||digt[i]==2&&digt[i+1]==6)
return ans;
}
return ans+1;
}
int main()
{
init();
int m,n;
while(cin>>m>>n)
{
if(m==0&&n==0) break;
cout<<solve(n)-solve(m-1)<<endl;
}
return 0;
}
/*
最近学习数位dp的一道题目，题目说给定一个区间[l,r];
求出[l,r]中不包含4和62的数字的个数。
我们定义数组f[i][j],表示i为数(假设i=2，即范围为10-99)中以j开头满足情况的数的个数。
那么f[i][j]=∑f[i-1][k];条件是j！=4&&!(j==6&&k==2),那么我们打表就可以完成准备工作
接下来就是求解了，既然是就出范围内的值，那么我们可以转化成：sum[i,j]=sum[0,j]-sum[0,i-1];
那么我们的任务就是构造这个sum函数；
我们以546为例子：首先能看到546是一个三位数，所以我们应该先把500以下的sum直接加和
即：ans+=∑sum[3][i](i<5)
然后去掉5，剩下46，接下来就是两位数的计算，即：ans+=∑sum[2][i](i<4)
接着去掉4，然后我们发现剩下的数都是40+，其中包括了4，所以不需要在计算，所以到这计算完成。
需要注意的是，按照这种计算方式，如果给定的数n本身就是一个满足情况的数，左后需要在ans的情况上+1。
*转载请注明出处，谢谢。
*/
原文：http://blog.csdn.net/knight_kaka/article/details/38235807