不要62

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 34510    Accepted Submission(s): 12484

Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如:
62315 73418 88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。
 
Input
输入的都是整数对n、m(0<n≤m<1000000),如果遇到都是0的整数对,则输入结束。
 
Output
对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。
 
Sample Input
1 100
0 0
 
Sample Output
80
 
Author
qianneng
 
Source
 
Recommend
lcy

/*
第一遍直接用搜索搞得,300多ms,第二次明白了dp数组的用处,只用了15ms
dp数组的作用就是把每次搜到的状态都记录下来,等到再次搜到相同条件的时候,就不用继续递归下去了,直接调用答案,所以时间上会省时不少
*/
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#define N 100
using namespace std;
/*
这个题我感觉没看懂给的数位DP用搜索就搞了,我下去再看看
*/
int g[];//一个数的每一位数,下标从1到len表示的是从个位到最高位
int dp[N][N];//dp[i][j]表示当前剩余位数为i时当前位上有无6的状态为j是的状态;
int dfs(int len,bool s,bool f)//剩下的位数,当前位置是不是6,选择数字的时候有没有限制,遍历的数字不能你要求的这个数还大
{
if(len<)
return ;//找到一个终点了就输出一种解法
if(!f&&dp[len][s]!=-)
return dp[len][s];
int cur=;
int fmax=f?g[len]:;//有限制只能选这一位上的数,没限制的话能选九位
for(int i=;i<=fmax;i++)
{
if(i==||(s&&i==)) continue;//不能有4,并且下两位不能是62
cur+=dfs(len-,i==,f&&(i==fmax));
//cout<<cur<<endl;
}
if(!f)
dp[len][s]=cur;
return cur;
}
int f(int x)
{
int len=;
while(x!=)//将每一位数都存到数组中
{
g[len++]=x%;
x/=;
}
memset(dp,-,sizeof dp);
//cout<<"len="<<len<<endl;
return dfs(len-,false,true);
}
int main()
{
//freopen("in.txt","r",stdin);
int a,b;
while(scanf("%d%d",&a,&b)!=EOF,(a||b))
printf("%d\n",f(b)-f(a-));
return ;
}

最新文章

  1. C#面向对象设计模式纵横谈——4.Builder 生成器模式(创建型模式)
  2. 微信小程序之明源商城系列-01-商城介绍及开发准备
  3. 配置自己的OpenGL库,glew、freeglut库编译,库冲突解决(附OpenGL Demo程序)
  4. 【java并发】传统线程技术中创建线程的两种方式
  5. bootstrap学习&lt;三&gt;打开模态窗体
  6. Qt 无法解析外部文件2001,2019之类的
  7. [转]Linux进程间通信——使用信号
  8. Unity 预处理命令
  9. javah的使用
  10. Java转Ruby【快速入门】
  11. 很详细的Django入门详解
  12. 两台主机,ssh端口不同,如何拷贝文件
  13. 为什么delete指针后指针设为null(已解答)
  14. List&lt;T&gt;常用操作
  15. webapi 统一处理时间格式
  16. SR锁存器
  17. 下拉列表控件实例 ComboBoxControl
  18. Oracle启动两个监听
  19. LPC43xx双核笔记
  20. js中取小数整数部分函数;取小数部分

热门文章

  1. windows10 下安装node失败 出现2502 2503的解决办法
  2. JS--微信浏览器复制到剪贴板实现
  3. Java的基本程序设计结构【2】
  4. The Moving Points hdu4717
  5. http://codeforces.com/problemset/problem/712/D
  6. 记一次Java的内存泄露分析
  7. thinkphp增删改查
  8. 系统出现异常: too many values to unpack (expected 2)
  9. 使用路由延迟加载 Angular 模块
  10. vue2购物车ch2-(商品列表显示)