HDU 3555 Bomb【数位DP】

数位DP第三题。学习ing~

题目传送门：这里

题目大意：

求$[1,x]$中含有$49$的数的个数。$T$次询问，$1 \leq T \leq 10000$，$1 \leq x \leq 2^{63}-1$。

前面讲的貌似是第一种数位DP的方法啦，现在我们来讲第二种。

这种一般用三个dp数组来表达，好像叫“有穷自动机”（雾？）好高端。

本题的话，$f[i,0]$表示长度小于等于$i$且不含$49$的数的个数，$f[i,1]$表示长度等于$i$且最高位含有$9$的不含$49$的数的个数，$f[i,2]$表示长度小于等于$i$含$49$的数的个数。

听起来十分的饶舌，但是很好写转移方程。

对于$f[i,0]$，长度小于等于$i$不含$49$的个数：那么就把长度小于等于$i-1$不含49的个数乘10就好了吧！（捂脸），不对，还要减去长度等于$i-1$最高位含有$9$的不含$49$的个数。所以$f[i,0]=f[i-1,0] \times 10 - f[i-1,1]$。

对于$f[i,1]$，长度等于$i$的最高位为$9$的不含$49$的个数，那么就是长度小于等于$i-1$的不含49的个数，第$i$位填个$9$就好啦！好有道理，那么$f[i,1]=f[i-1,0]$。

对于$f[i,2]$，表示长度小于等于$i$含$49$的数的个数，等于长度小于等于$i-1$的含$49$的个数，最高位随便填都行，完了吗？没有！还要加上长度为$i-1$最高位为$9$的不含$49$的个数，因为填一个$4$就造出$49$了！所以，$f[i,2]=f[i-1,2] \times 10 + f[i-1,1]$。

好啦，$dp$预处理好了，下面就是正常的处理程序啦。

关于状态的设计一般有3个方面：

$f[i,0]$表示长度小于等于$i$且不符合条件的数的个数，$f[i,1]$表示长度等于$i$且（不）符合条件（+特殊限制）的的数的个数，$f[i,2]$表示长度小于等于$i$符合条件的数的个数。

特殊限制一般就有几个方面，比如本题要49，特殊限制就是最高位是9；因为这样设计，下一个填4就会造出49，好进行转移。上一题数位dp：不要62好像也可以这样来做呀，诸君稍等，容我打打代码。

$2015/08/21/18:30$已更新，下一篇博文啦。

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

typedef unsigned long long ull;

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

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

ull calc(ull x) {
	ull cnt=0; bool flag=0;
	for (int i=dn;i>=1;--i) {
		cnt+=dp[i-1][2]*d[i];
		if(flag) cnt+=dp[i-1][0]*d[i];
		else {
			if(d[i]>4) cnt+=dp[i-1][1];
			if(d[i+1]==4&&d[i]==9) flag=1;
		}
	}
	if(flag) cnt++;
	return cnt;
}

int main() {
	ull x;
	scanf("%d",&T);
	getdp();
	while(T--) {
		scanf("%I64u",&x);
		getd(x);
		printf("%I64u\n",calc(x));
	}
	return 0;
}