不要62(数位dp板子题)

描述

传送门:hdu-2089

 杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如:
62315 73418 88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input

输入的都是整数对$n, m\ (0<\ n ≤\ m<1000000)$,如果遇到都是0的整数对,则输入结束。

Output

对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。

Examples

  • intput

    1
    2
    1 100
    0 0
  • output

    1
    80

思路

  • 数位dp,状态其实就只有两个,pos: 当前枚举的位数, state: 前一位是否为6
  • 在每一位枚举的时候就判断一下当前位是不是4,是否前一位为6且当前位为2。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define repd(i,a,n) for(int i=n;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e6+5;
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod=1e9+7;
typedef long long ll;

int dp[10][2],a[10]; //dp[i][0]表示i位置,前面一个不是6时有多少个符合的数
//dp[i][1]表示i位置,前面一个是6时有多少个符合的数

int dfs(int pos,int state,int limit){ //pos: 当前数位 , state: 1/0 前面一位 是/不是 6, limit: 前一位是否枚举到了最高位
if(pos==-1) return 1; //枚举到最后一位,符合条件(不然前面就return了
if(!limit&&~dp[pos][state]) return dp[pos][state]; //前一位没有枚举到最高位且这个状态记录过了,直接return
int up = limit ? a[pos]:9; //上限
int sum=0;
rep(i,0,up){ //枚举当前位
if(i==4||state&&i==2) continue; //如果这位是4 或者 前一位是6且当前位是2,continue
sum+=dfs(pos-1,i==6,limit&&i==a[pos]); //dfs
}
if(!limit) dp[pos][state]=sum; //记录状态
return sum;
}

int f(int x){
int pos=-1;
while(x){
a[++pos]=x%10;
x/=10;
}
dfs(pos,0,1);
}

int main(){
int n,m;
CRL(dp,-1); //由于一个数符不符合条件和输入无关,只和它自身有关,所以初始化可以放在外面。
while(scanf("%d%d",&n,&m)&&(n||m))
printf("%d\n",f(m)-f(n-1));
return 0;
}
-------------本文结束 感谢您的阅读-------------

本文标题:不要62(数位dp板子题)

文章作者:Armin

发布时间:2019年07月20日 - 18:07

最后更新:2019年07月20日 - 19:07

原始链接:http://x-armin.com/不要62/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

小礼物走一波