不要62

题意:给定区间,求在这个区间中有多少个数字,不包含4且不包含62;

这道题作为数位DP的入门题;

暴力也是可以过

#include<cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std; const int maxn =1e6+;
int a[maxn];
bool check(int x)
{
while(x>)
{
if(x%==)return true;
if(x%==)return true;
x/=;
}
return false;
}
int main(){
int sum = ;
for(int i=;i<=;i++)
{
if(check(i)){a[i]=sum;continue;}
sum++;
a[i]=sum;
}
int l,r;
while(~scanf("%d%d",&l,&r)&&l+r)
{ printf("%d\n",a[r]-a[l-]);
} return ;
}

当然数位DP更快,利用记忆化DFS

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std; int dp[][],digit[];
int dfs(int pos,bool pre_6,bool limit)
{
if(pos==)return ;
if(!limit&&dp[pos][pre_6]>=)return dp[pos][pre_6];
int ans=,num=limit?digit[pos]:;
for(int i=;i<=num;i++)
{
if(i==||(pre_6&&i==))
continue;
ans += dfs(pos-,i==,limit&&i==num); //只有之前有限制现在的达到了上限才能构成限制
}
return limit?ans:dp[pos][pre_6] = ans;//如果有限制,那么就不能记忆化,否则记忆的是个错误的数. }
int solve(int x)
{
int len = ;
while(x>)
{
digit[++len]=x%; //将数字存在digit数组中
x/=;
}
return dfs(len,false,true);
} int main(){
memset(dp,-,sizeof(dp));
int l,r;
while(scanf("%d%d",&l,&r),l+r)
{
printf("%d\n",solve(r)-solve(l-));
}
return ;
}

最新文章

  1. External Configuration Store Pattern 外部配置存储模式
  2. 时间管理的若干Tips
  3. JAZZ
  4. ashx
  5. PHP面向对象的标准
  6. jquery操作cookie {分享}
  7. 第二百九十六天 how can I 坚持
  8. phpcms v9和discuz X3.1实现同步登陆退出论坛(已实现)
  9. 14-C语言宏
  10. 简述.jpg .Gif .png-8 .png-24的区别
  11. 第十六次 ccf 201903-2 二十四点
  12. 关于Oracle重新启动
  13. Codeforces 633F The Chocolate Spree 树形dp
  14. JS膏集01
  15. bash执行命令分别输出正常日志和错误日志
  16. applyColorMap()研究(如果我对现有的colormap不满意,那么如何具体来做)
  17. redis的高级事务CAS(乐观锁)
  18. SQL Server 2012 books
  19. hadoop学习笔记(四):hdfs常用命令
  20. jmeter3.3—插件管理器的安装

热门文章

  1. tomcat 启动是 jdbc警告
  2. drf之序列化
  3. 【JDK】JDK源码分析-AbstractQueuedSynchronizer(1)
  4. JavaFX Metro UI 和 开发库
  5. python3学习-requests使用
  6. Android 打包时 Keep 住某些方法或类
  7. Promise对象的resolve回调函数和reject回调函数使用
  8. Mysql超详解
  9. Java学习|Exception和Error有什么区别?
  10. 阿里巴巴_java后端面经