学步园

原题链接  http://acm.hdu.edu.cn/showproblem.php?pid=4278

题意： 给出一个数N，从1数到N，要求跳过 3和 8 两个数字，问能数多少个数字 

可以用数位DP做，

还有一种更简单的方法，题意中把 3 8 两个数去掉，其实就相当于八进制，所以把十进制转换为八进制就可以了

下面给出数位dp的代码

#include<iostream>
using namespace std;
//dp[i][0] 不含3 8
//dp[i][1] 含 3 8
int dp[25][2];
void init(){
	int i;
	dp[0][0]=1;
	dp[0][1]=0;
	dp[1][0]=8;
	dp[1][1]=2;
	for(i=2;i<=10;i++){
		dp[i][0]=8*dp[i-1][0];
		dp[i][1]=10*dp[i-1][1]+2*dp[i-1][0];
	}
}
int f(int xx){
	int x[105];
	int len=0;
	while(xx){
		x[len++]=xx%10;
		xx/=10;
	}
	x[len]=0;
	int i;
	bool flag=false;
	int cnt=0;// 包含 3 8 的个数
	for(i=len-1;i>=0;i--){
		cnt+=x[i]*dp[i][1];
		if(flag){
			cnt+=x[i]*dp[i][0];
		}
		else{
			if(x[i]>3)
				cnt+=dp[i][0];
			if(x[i]>8)
				cnt+=dp[i][0];
			if(x[i]==3 || x[i]==8)
				flag=true;
		}
	}
	return cnt;
}
int main(){
	int x;
	init();
	while(scanf("%d",&x),x){
		cout<<x<<": ";
		cout<<x-f(x+1)<<endl;
	}
	return 0;
}