题意: 给定一个区间[n,m] (0< n ≤ m<1000000),找出不含4和'62'的数的个数 (ps:开始以为直接暴力可以。。貌似可以，但是直接TLE了2333).其实是数位DP的入门题；
- 初探数位DP:写的很详细(看完就不必看我的代码了..)
- f[i,j]:位置长度为i以j开头的符合条件的数的个数；(一般的dp式子中，第二个参数依题意)；这就直接可以推出f[i,j] = f[i,j] + f[i-1,k] ( j != 6 || k != 2)
- 开始打表打出所有的f[i][k];之后就sum(a)计算小于a的符合要求的数的个数(相当于树状数组)；里面从高位起，看小于a的情况数(只看高位)，这就导致了当高位不符合
- **范围计数详见sum();
#include<bits/stdc++.h>
using namespace std;
int f[][];
void init()
{
f[][] = ;
for(int i = ;i <= ;i++){
for(int j = ;j <= ;j++)
for(int k = ;k <= ;k++)
if(j != && (j != || k != ))
f[i][j] = f[i][j] + f[i-][k];
}
}
int sum(int a)
{
int digit[]={},len = ;
while(a){
digit[++len] = a % ;
a /=;
}
int ans = ,i,j;
for(i = len;i > ;i--){ //哪一位小于n;
for(j = ;j < digit[i];j++)//当j = 0时，代表了所有位数比n少的情况，即049,009均包括了，所以在后面出现的数其实是最高位和n相同的数;
if(j != && (j != || digit[i+] != ))
ans += f[i][j];
if(j == || (j == && digit[i+] == ))
break;
}
return ans;
}
int main()
{
init();
int a,b;
while(scanf("%d%d",&a,&b) == && a + b){
printf("%d\n",sum(b+) - sum(a));
}
}
用递归写起来更清爽，递归版本:
#include<bits/stdc++.h>
using namespace std;
int dp[][];
int bit[];
int dfs(int pos,int d,int on = )
{
if(pos == ) return ;
int ans = dp[pos][d];
if(!on && dp[pos][d] != -) return ans;
ans = ;
int e = (on? bit[pos]:);
for(int i = ;i <= e; i++)
if(i != && (d != || i != ))
ans += dfs(pos - ,i,i == e && on);
if(!on) dp[pos][d] = ans;
return ans;
}
int cal(int a)
{
int tot = ;
while(a){
bit[++tot] = a%;
a /= ;
}
return dfs(tot,);
}
int main()
{
memset(dp,-,sizeof(dp));
int n,m;
while(scanf("%d%d",&n,&m) == && n + m){
//cout<<cal(m)<<" "<<cal(n - 1)<<" ";
printf("%d\n",cal(m) - cal(n - ));
}
}