ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[HDUOJ]Bomb(数位dp)

2022年5月11日 1149点热度 0人点赞 0条评论

题目传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ hduoj 数位dp 模板题 算法 算法竞赛
最后更新:2022年7月9日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 题目大意
  • 思路
  • 代码

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号