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$已更新，下一篇博文啦。