前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数位DP - HDU 2089

数位DP - HDU 2089

作者头像
ACM算法日常
发布2018-12-24 14:43:46
4390
发布2018-12-24 14:43:46
举报
文章被收录于专栏:ACM算法日常

其实数位DP就是优化计数的过程,就是dfs+记忆化数组,题目会给一个上界或者下界,然后让你统计范围内符合要求的数量,如果事事用爆破的话就太有病了!除非我吃拧了!小学生都不会干的傻事!

解题步骤:

1.处理数位函数 cal() solve() ...自己命名 > 将输入的数进行分解

2.dfs的函数 => 执行的是数位dp(dfs+记忆化搜索)

给个具体的例子吧 - HDU 2089

不要62

杭州人称那些傻乎乎粘嗒嗒的人为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

其实,整个题目的过程就是这个题的思路,说白了就是给每一位标记,然后dfs下的一个记忆暴搜,别的没嘛。

如果还是不明白的话,我的博客倒是有两篇数位DP的模板,方便大家copy.

另外我记得电科大有一集数位dp,在bi站上讲得相当好。由于我不是打DP位的献丑了

代码语言:javascript
复制
///HDU 2089

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

int digit[20];
LL dp[20][2];//当前数位 含有6时,区间内有多少数 没有62 当前数位不是6时 区间内有多少数 没有62 !!!

///if4=>status(状态)是否是6
LL dfs(int len,bool if6,bool limit)
{
    //len表示当前位 !!   if6表示len的上一位是否是6!!   limit表示当前位的最大约束 !!
    if(len==0) return 1ll;//个位数时  满足条件的个数仅为一!
    if(!limit && dp[len][if6]) return dp[len][if6];
    //当前数位的数 没有到达上界,且统计过  则直接返回!!
    //典型的记忆化 的语句!!

    LL cnt=0,up_bound=(limit?digit[len]:9);//当前位  上界的约束!!
    for(int i=0;i<=up_bound;++i){
        if(if6 && i==2)///=>找到一个49
            continue;
        if(i==4) continue;//剪枝
        cnt+=dfs(len-1,i==6,limit&&i==up_bound);
        /*为下一位设上限 !!*/
    }
    if(!limit) dp[len][if6]=cnt;
    return cnt;
//如果这一位 不含上界则作为完整的数 可以记录下来 !!
//统计在数位上  下次dfs时以便遇见直接返回!!

}
///统计的是没有62的个数
LL solve(LL num){
    int k=0;
    while(num){
        digit[++k]=num%10;
        num/=10;
    }
    return dfs(k,false,true);//dfs记忆爆搜
}

int main(){

    LL N,M;
    while(cin>>N>>M && N+M){

    //注意0 0 的特判  当n=0时,n-1=-1,这时solve(-1)代入跑dfs,得出的结果就还真是0
    //所以我感觉这套板子的强度很大!!!   满足卡特判的活!!!
    //精髓在 !!!卡特判!!!
        cout<<solve(M)-solve(N-1)<<endl;
    }
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-12-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 解题步骤:
  • 1.处理数位函数 cal() solve() ...自己命名 > 将输入的数进行分解
  • 2.dfs的函数 => 执行的是数位dp(dfs+记忆化搜索)
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档