HDU 3555 Bomb 【数位DP】

tonyfang posted @ 2015年8月21日 17:56 in HDU with tags c++ HDU , 341 阅读

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;
}

登录 *


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