【Hdu2089】不要62(数位DP)
2024-08-21 16:45:50
Description
题目大意:给定区间[n,m],求在n到m中没有“62“或“4“的数的个数。
如62315包含62,88914包含4,这两个数都是不合法的。
0<n<=m<1000000
Solution
数位DP,首先预处理数组\(F[i][j]\),表示位数为\(i\),开头为\(j\)时,满足条件的数的个数
对于区间\([l,r]\)转化为求\([0,r]-[0,l)\)即可
对于区间\([0,n]\)将n按位数存储分别计算,
这样最后算出来的个数实际上为\([0,r)\)的,所以计算时上界应该+1
计算个数时如遇到4或62直接退出,详见代码
Code
#include <cstdio>
#include <cstring>
int n,m,f[10][10];
inline void Init(){
memset(f,0,sizeof(f));
f[0][0]=1;
for(int i=1;i<=7;++i)
for(int j=0;j<=9;++j)
for(int k=0;k<=9;++k)
if(j!=4&&!(k==2&&j==6))//注意6和2的位置
f[i][j]+=f[i-1][k];
}
int DP(int k){
if(!k) return 0;
int len=0,d[10],r=0;
while(k){
d[++len]=k%10;
k/=10;
}
d[len+1]=0;
for(int i=len;i;i--){
for(int j=0;j<d[i];++j)
if(j!=4&&!(j==2&&d[i+1]==6))
r+=f[i][j];
if(d[i]==4||(d[i]==2&&d[i+1]==6))//直接跳出
break;
}
return r;
}
int main(){
while(~scanf("%d%d",&n,&m)&&n+m){
Init();
printf("%d\n",DP(m+1)-DP(n));
}
return 0;
}
最新文章
- iframe的自适应高度
- [ACM_几何] Pipe
- 以Access为支撑,书写一个C#写入记录的案例
- JSP的JSTL标签使用
- Mac Pro 安装 最新版的 SVN 1.9.4
- 【BZOJ】【3207】花神的嘲讽计划 I
- SVN备份教程(三)
- 《Dive into Python》Chapter 2 and Chapter 3 笔记
- Entity Framework 重写OnModelCreating,控制生成表名的单复数
- Java快速排序
- Python第三方库安装技巧
- jaspersoft studio 的初级入门(一)
- 笔记:MyBatis Mapper XML文件详解 - 映射和参数
- seleium_元素定位
- redis4.X
- log4j日志日记记录使用教程
- 由于没有公钥,无法验证下列签名: NO_PUBKEY 54422A4B98AB5139
- Objecttive-C各种问题
- 解决 Invalid signature file digest for Manifest 问题
- Oracle date和timestamp区别