hdu2089不要62加强版
2018-06-27 10:00:51来源:未知 阅读 ()
不要62
时间限制:1sec
内存限制:3MB
题目描述
杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。
不吉利的数字为所有含有4或62的号码。例如:
62315 73418 88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。
输入
输入的都是整数对n、m(0<=n<=m<2147483647),如果遇到都是0的整数对,则输入结束。
输出
对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。
样例输入
1 100
0 0
样例输出
80
提示
数位DP
一看,是没有什么问题,不看内存限制,打表都能过。
只要开一个数组存,打表就过了。
多简单的事情,是吧。
只要大约500000的数组。
但是它正好把这个给卡了。
其实也不是没有办法。
但很难AC。
所以咱们就只能用数位DP做。
因为题目叫我们用数位DP做啊。
#include<bits/stdc++.h> using namespace std; int dp[15][10]; void init(){ memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=11;i++){ for(int j=0;j<=9;j++){ for(int k=0;k<=9;k++){ if(j!=4&&!(j==6&&k==2)) dp[i][j]+=dp[i-1][k]; } } } } int solve(int n){ int dight[15]; int len=0,ans=0; while(n!=0){ dight[++len]=n%10;n/=10; } dight[len+1]=0; for(int i=len;i>=1;i--){ for(int j=0;j<dight[i];j++){ if(j!=4&&!(dight[i+1]==6&&j==2))ans+=dp[i][j]; } if(dight[i]==4||(dight[i]==2&&dight[i+1]==6))break; } return ans; } int main(){ init(); int l,r; while(1){ scanf("%d%d",&l,&r); if(l+r==0)break; printf("%d\n",solve(r+1)-solve(l)); } return 0; }
代码虽然不是我想的,但貌似很简单的样子。
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:5971 打击犯罪
下一篇:C++实现的控制台-贪吃蛇
- p1969积木大赛 2019-02-25
- 第四章 基本编程技术 2018-12-04
- C++ 学习笔记(二) const的加强 2018-08-26
- BZOJ4407: 于神之怒加强版(莫比乌斯反演 线性筛) 2018-07-19
- 洛谷P3796 【模板】AC自动机(加强版) 2018-07-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash