[Hdu3555] Bomb(数位DP)
2024-09-01 08:12:12
Description
题意就是找0到N有多少个数中含有49。
\(1\leq N \leq2^{63}-1\)
Solution
数位DP,与hdu3652类似
\(F[i][state]\)表示位数为i,包含49状态为state时的方案数
注意开\(long long\)
Tips
注意N范围很大,位数不止10位!!
Code
#include <cstdio>
#include <cstring>
#define ll long long
int d[20];
ll dp[20][3],n,T;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll dfs(int p,int sta,int lim){
ll &tmp=dp[p][sta],r=0;
if(!lim&&tmp!=-1) return tmp;
if(!p) return sta==2;
int mx=lim?d[p]:9;
for(int i=0;i<=mx;++i){
int t=0;
if(sta==2) t=2;
else if(sta==1&&i==9) t=2;
else if(i==4) t=1;
r+=dfs(p-1,t,lim&&(i==mx));
}
return lim?r:tmp=r;
}
int main(){
T=read();
memset(dp,-1,sizeof(dp));
while(T--){
n=read();
int len=0;
while(n){
d[++len]=n%10;
n/=10;
}
d[len+1]=0;
printf("%lld\n",dfs(len,0,1));
}
return 0;
}
最新文章
- CSS颜色名称和颜色值
- log4net学习笔记
- Microsoft Mole原理及常见问题整理
- ACM——数的计算
- SignalR2.0开发实例之——私聊
- Oracle基于学习3--Oracle创建用户和授权
- MVC4新功能...压缩和合并js文件和样式文件
- 在centos 6.8下安装docker
- Oracle中如何导出存储过程、函数、包和触发器的定义语句?如何导出表的结构?如何导出索引的创建语句?
- MySql下实现先排序后分组
- 如何用jquery获取form表单的值
- Go学习笔记07-结构体与方法
- 第三周Access的总结
- swap file ";*.swp"; already exists!
- 用Metaclass实现一个精简的ORM框架
- Odoo中的约束
- [HTML/CSS]div显示在object、embed之上~
- codevs.cn 2776寻找代表元 最大流解法
- SpringCloud-分布式配置中心(config)
- QT 实现拖放功能
热门文章
- 4.0.3的mongodb 安装和java使用
- sqlserver2008执行200M以上的大脚本文件,打开脚本总是报“未能完成操作,存储空间不足”
- 粗看ES6之变量
- Vue.js(2.x)之Class 与 Style 绑定
- keil 系列问题
- Cocos2d-x v3.1 核心类Director,Scene,Layer和Sprite(六)
- Unity调用外部摄像头,全屏显示摄像头画面
- python基础-字符串操作
- zabbix 监控项
- help.hybris.com和help.sap.com网站的搜索实现