[HDUOJ]Bomb（数位dp）

题目传送门：Problem - 3555 (hdu.edu.cn)

题目大意

给定一个N，求[1, N]范围内的数字转换形成的字符串中包含"49"的数字。 (1 <= N <= 2^63-1)

思路

因为数据太大了，所以直接前缀和肯定行不通，所以需要数位dp。

典型的数位dp模板题。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int a[20];
int dp[20][20];

int dfs(int pos, int pre, bool limit) //得到不含有49的数字个数 
{
	if(pos == 0)return 1;
	if(!limit && dp[pos][pre] != -1)return dp[pos][pre];
	//!limit保证不被限制，防止出现状态冲突 
	int res = 0, up = limit ? a[pos] : 9;
	for(int i = 0;i <= up; ++ i)
	{
		if(pre == 4 && i == 9)continue; //如果遇到了49这个数字就跳过 
		res += dfs(pos - 1, i, limit && i == a[pos]);
	}
	if(!limit)dp[pos][pre] = res;
	//保存和读取dp的信息都需要保证!limit 
	return res;
}

int solve(int N) //得到[0, N]之间不含有49的数字个数 
{
	int k = 0;
	while(N)a[++ k] = N % 10, N /= 10;
	return dfs(k, 0, 1);
}

signed main()
{
	memset(dp, -1, sizeof dp);
	int T;cin >> T;
	while(T --)
	{
		int N;cin >> N;
		printf("%lld\n", N + 1 - solve(N));
	}
	return 0;
}