数位 DP 入门：HDU 3555 Bomb

简单来说，数位 DP 大概就是把一个数字拆开按位进行 DP 的一种思想。

HDU 3555 Bomb

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the power of the blast would add one point. Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

Hint

数位 DP 的典型入门题，解法很多。

Analysis #1

这题“包含 49 的数字数量”比较难构造，所以我们决定构造“不包含 49 的数字数量”。

DP 构造

F[i][j]：最高位为 j 的 i 位数字中不包含 49 的数字数量。

$F(i,j) = \sum_{k\in [0,9]}^{k \not = 9 \text{或} j \not = 4} F(i-1,k)$

inline void make_dp(){
	for (int i=0;i<=9;i++) f[1][i]=1;
	for (int i=2;i<=22;i++)
	for (int j=0;j<=9;j++)
	for (int k=0;k<=9;k++){
		if (j==4&&k==9) continue;
		f[i][j]+=f[i-1][k];
	}
}

答案累计

首先将数字按位分离，然后按位统计。

对于从高到低第 $i$ 位数字 $A_i$，首先肯定要累计上 $\sum_{j=0}^{j < A_i} F(i,j)$，也就是这一位小于 $A_i$ 的数字数量。至于这一位等于 $A_i$ 的情况，就是之后处理的了。所以需要判断一下：如果出现了 49 这个数字就退出。

inline int calculate(int x){
	int ret=0;
	spread_number(x);
	for (int i=a[0];i>=1;i--){
		for (int j=0;j<a[i];j++) ret+=f[i][j];
		if (a[i]==9&&a[i+1]==4) break;
	}
	return ret;
}

代码

/*
 * Vjudge CONTEST257056 数位DP专题练习
 * B - Bomb
 * 180927 By SkyWT
 */

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>

using namespace std;

#define memset_clear(_) memset(_,0,sizeof(_))
#define memset_clear_tre(_) memset(_,1,sizeof(_))
#define memset_clear_reg(_) memset(_,-1,sizeof(_))
#define memset_clear_max(_) memset(_,0x3f,sizeof(_))
#define memset_clear_min(_) memset(_,0x80,sizeof(_))
#define sqr(_) ((_)*(_))

#define write(_) cout<<#_<<" = "<<_<<endl
#define write_2(_,__) cout<<#_<<" = "<<_<<" , "<<#__<<" = "<<__<<endl
#define write_3(_,__,___) cout<<#_<<" = "<<_<<" , "<<#__<<" = "<<__<<" , "<<#___<<" = "<<___<<endl

#define int long long

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}

int T,n;
int f[25][11],a[25];

inline void make_dp(){
	for (int i=0;i<=9;i++) f[1][i]=1;
	for (int i=2;i<=22;i++)
	for (int j=0;j<=9;j++)
	for (int k=0;k<=9;k++){
		if (j==4&&k==9) continue;
		f[i][j]+=f[i-1][k];
	}
}

inline void spread_number(int x){
	memset_clear(a);
	while (x) a[++a[0]]=x%10,x/=10;
}

inline int calculate(int x){
	int ret=0;
	spread_number(x);
	for (int i=a[0];i>=1;i--){
		for (int j=0;j<a[i];j++) ret+=f[i][j];
		if (a[i]==9&&a[i+1]==4) break;
	}
	return ret;
}

signed main(){
	make_dp();
	T=read();
	while (T--){
		n=read();
		printf("%lld\n",n+1-calculate(n+1));
	}
	return 0;
}

Analysis #2

这种方法相较上一种，空间和时间上只达到了常数的优化。不过还是值得研究下～

DP 构造

这个 DP 的定义比刚才的要简单一点：

• F[i][0]：数字长度为 i，首位为任意数字，不包含 49 的数字数量
• F[i][1]：数字长度为 i，首位为 9，不包含 49 的数字数量
• F[i][2]：数字长度为 i，包含 49 的数量

转移方程如下：

$F(i,0)=F(i-1,0)\ast 10-F(i-1,1)$

（很好理解，要减去出现了 49 的情况）

$F(i,1)=F(i-1,0)$

$F(i,2)=F(i-1,2)\ast 10+F(i-1,1)$

（要加上这位为 4、后一位为 9 的情况）

答案累计

答案的累计和上面解法差不多。

Analysis #3

这题其实还可以用记忆化搜索。数位 DP 用记忆化搜索解决会很方便～

代码

以下是 HEXU 大佬的代码……

#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
const int N = 100 + 5;

ll f[N][N];
int digit[N];

ll dfs(int pos, int flag, int limit) {
	if (pos <= 0) return 1;
	if (! limit && f[pos][flag] != -1) return f[pos][flag];
	int up = limit ? digit[pos] : 9; ll cur = 0;
	
	for (int i = 0; i <= up; ++ i) {
		if (flag == 1 && i == 9) continue;
		cur += dfs(pos - 1, i == 4, limit && i == up);
	}
	return limit ? cur : f[pos][flag] = cur;
}

ll Solve(ll x) {
	memset(digit, 0, sizeof(digit)); int len = 0;
	for (; x; x /= 10) digit[++ len] = x % 10;
	return dfs(len, 0, 1);
}

int main(void) {
	memset(f, -1, sizeof(f));
	int T; scanf("%d", &T);
	while (T --) {
		ll r; scanf("%lld", &r);
		printf("%lld\n", r + 1 - Solve(r));
	}
	return 0;
}