hdu 2089（dp）

青旅半醒 2022-08-20 13:27 14阅读 0赞

题意：给出一个区间，求这个区间里面的数字一共有多少个数字其中不含数字4并且没有连续的62 。

例如，4,14,412,162等等数字就不满足要求。

分析：

网上都说这题是数位dp，好像是的。可是我还没有入门数位dp，就是用的普通的dp来写的。

dp\[i\]表示的是在区间(1,i)之间满足要求的数字的个数，递推公式为：dp\[i\] = dp\[i-1\]+0/1   .

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    int const maxn = 1000005 ;
    int dp[maxn];
    //dp[i] 表示的是从1到i之间的数的个数
    
    bool Judge(int n)
    {
        while(n)
        {
            if(n%10==4||n%100==62)return false;
            n/=10;
        }
        return true ;
    }
    
    void cal()
    {
        memset(dp,0,sizeof(dp));
        dp[1] = 1 ;
        for(int i = 2 ; i < maxn ; i++)
        {
            if(Judge(i))dp[i] = dp[i-1]+1 ;
            else dp[i] = dp[i-1] ;
        }
    }
    
    int main()
    {
        cal();
        int n,m;
        while(scanf("%d%d",&n,&m)&&n>0&&m>0)
        {
            printf("%d\n",dp[m]-dp[n-1]);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，14人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 2089

题目传送门：[http://acm.hdu.edu.cn/showproblem.php?pid=2089][http_acm.hdu.edu.cn_showproblem.p

浅浅的花香味﹌/ 2023年05月21日 15:20/ 0 赞/ 7 阅读

相关 Hdu 2089 不要62 (暴力/数位dp)

应该属于数位dp的一题，暴力方法可过就先偷懒了…… 第二段代码是别人的，转化成字符串进行处理 include <cstdio> __int64 d

曾经终败给现在/ 2022年10月31日 01:44/ 0 赞/ 157 阅读

相关 HDU 2089-不要62(数位DP)

不要62 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

蔚落/ 2022年08月22日 13:22/ 0 赞/ 161 阅读

相关 hdu3555 + 2089 (数位dp入门)

hdu3555 给出数字n，要求1到n范围内所有的数字中出现连续49的数字的个数。n很大。例如500，那么出现连续49的数字有49,149,249,349,449，490

悠悠/ 2022年08月20日 14:18/ 0 赞/ 16 阅读

相关 hdu 2089（dp）

题意：给出一个区间，求这个区间里面的数字一共有多少个数字其中不含数字4并且没有连续的62 。例如，4,14,412,162等等数字就不满足要求。分析：网上

青旅半醒/ 2022年08月20日 13:27/ 0 赞/ 15 阅读

相关【数位DP+记忆化搜索】不要62 HDU - 2089

Think: 1知识点：数位DP+记忆化搜索 2思考：（1）：注意符合题意条件的判断（当ok为true的状态） 3题意：输入一个区间，判断这个区间内不含4且不

╰半橙微兮°/ 2022年06月08日 09:59/ 0 赞/ 221 阅读

相关 hdu 2089 不要62

Problem Description 杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不

怼烎@/ 2022年05月31日 02:13/ 0 赞/ 184 阅读

相关 HDU-2089 不要62

不要62 Problem Description 杭州人称那些傻乎乎粘嗒嗒的

迷南。/ 2022年05月03日 06:30/ 0 赞/ 184 阅读

相关 HDU2089 不要62

Problem Description 杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照

旧城等待，/ 2021年11月26日 07:22/ 0 赞/ 230 阅读

相关【hdu2089】不要62 [数位dp]

![1591261-20190611115344981-1062772141.jpg][]就搞不懂为什么我多预处理了几位就会炸然后放mzoj上还非要预处理8位真的要叫我去

红太狼/ 2021年11月17日 15:44/ 0 赞/ 294 阅读