HDU2089 不要62 【数位DP】之另一种方法

tonyfang posted @ 2015年8月21日 18:29 in HDU with tags c++ HDU , 300 阅读

上一种方法可以参见上一个这道题的题解。这题这份代码所采用的方法是我上一篇博文所介绍的。

注意的是,计数的时候因为不好统计,使用了逆向计数,即算出所有不吉利数的个数$cnt$,再用$x-cnt$即可。

 

# include <stdio.h>
# include <string.h>
using namespace std;


int dp[25][3];
int T;
//dp[i][0]:长度<=i的含62和4的数的个数  
//dp[i][1]:长度为i,且最高位含有2的不含62和4的数的个数  
//dp[i][2]:长度<=i的不含62和4的数个数
inline void getdp() {
	memset(dp,0,sizeof(dp));
	dp[0][2]=1;
	for (int i=1;i<=10;++i) {
		dp[i][0]=dp[i-1][0]*10+dp[i-1][2]+dp[i-1][1]; 
		dp[i][1]=dp[i-1][2];
		dp[i][2]=dp[i-1][2]*9-dp[i-1][1]; 
	}
}

int d[25],dn;
inline void getd(int x) {
	dn=0;memset(d,0,sizeof(d));
	while(x) d[++dn]=x%10,x/=10;
}

int calc(int x) {
	dn=0;memset(d,0,sizeof(d));int sum=x;
	while(x) {
		d[++dn]=x%10;
		x/=10;
	}
	int cnt=0; bool flag=0;
	for (int i=dn;i>=1;--i) {
		cnt+=dp[i-1][0]*d[i];
		if(flag) cnt+=dp[i-1][2]*d[i];
		else {
			if(d[i]>4) cnt+=dp[i-1][2];
			if(d[i+1]==6&&d[i]>2) cnt+=dp[i][1];
			if(d[i]>6) cnt+=dp[i-1][1];
			if(d[i]==4||(d[i]==2&&d[i+1]==6)) flag=1;
		}
	}
	if(flag) cnt++;
	return sum-cnt;
}

int main() {
	int x,y;
	getdp();
	while(~scanf("%d%d",&x,&y) && (x+y)) printf("%d\n",calc(y)-calc(x-1));
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter