学步园

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

第一次Ac数位DP 还是比较爽的

题意：给出 A和 B， 求出A至B中不包含4和62的数字的个数

上代码

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int dp[15][3];
//dp[i][0] 不存在不吉利数的个数
//dp[i][1] 不存在不吉利数且首位为2的数的个数
//dp[i][2] 存在不吉利数的个数
void init(){
	dp[0][0]=1;
	dp[0][1]=dp[0][2]=0;
	dp[1][0]=9;
	dp[1][1]=1;
	dp[1][2]=1;
	int i;
	for(i=2;i<=7;i++){
		dp[i][0]=dp[i-1][0]*9 - dp[i-1][1];
		dp[i][1]=dp[i-1][0];
		dp[i][2]=dp[i-1][2]*10 + dp[i-1][0] + dp[i-1][1];
	}

}//534 638
int DP(char a[]){
	bool flag=false;
	int ans=0;
	int i;
	int n=strlen(a);
	a[n]='0';
	for(i=0;i<n;i++){
		ans+=(a[i]-'0')*dp[n-i-1][2];
		if(flag){
			ans+=(a[i]-'0')*dp[n-i-1][0];
		}
		if(!flag && a[i]>'4')//包含4
			ans+=dp[n-i-1][0];
		if(!flag && a[i]>'6')//包含6的 ，62
			ans+=dp[n-i-1][1];
		if(!flag && i && a[i-1]=='6'&&a[i]>'2')//前一位为6，后一位大于2，有62
			ans+=dp[n-i][1];
		if(!flag && ( a[i]=='4' || i&&a[i-1]=='6'&&a[i]=='2')){  //高位有62 
			flag=true;
		}
	}
	int sum=0;
	for(i=0;i<n;i++){
		sum*=10;
		sum+=a[i]-'0';
	}
	return sum-ans;
}
int main(){
	char a[105],b[105];	
	init();
	while(scanf("%s%s",a,b)!=EOF){
		int la=strlen(a);
		int lb=strlen(b);
		if(a[0]=='0' && b[0]=='0'&& la==1 && lb==1)
			break;
		int i;
		int n; 
		n=strlen(b);
		i=n-1;
		if(b[n-1]=='9'){ while(i && b[i]=='9') { b[i]='0'; i--; } if(i!=-1) b[i]++; else { for(i=n-1;i>=0;i--) b[i+1]=b[i]; b[0]='1'; } }
		else b[n-1]++;  // b=b+1;
		cout<<DP(b)-DP(a)<<endl;
	}
	return 0;
}