FZU2109 Mountain Number——————数位DP-程序员宅基地

技术标签: BFS+DFS  动态规划  数位DP  

Mountain Number

Accept: 351 Submit: 875
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

One integer number x is called “Mountain Number” if:

(1) x>0 and x is an integer;

(2) Assume x=a[0]a[1]…a[len-2]a[len-1](0≤a[i]≤9, a[0] is positive). Any a[2i+1] is larger or equal to a[2i] and a[2i+2](if exists).

For example, 111, 132, 893, 7 are “Mountain Number” while 123, 10, 76889 are not “Mountain Number”.

Now you are given L and R, how many “Mountain Number” can be found between L and R (inclusive) ?

Input
The first line of the input contains an integer T (T≤100), indicating the number of test cases.

Then T cases, for any case, only two integers L and R (1≤L≤R≤1,000,000,000).

Output
For each test case, output the number of “Mountain Number” between L and R in a single line.
Sample Input
3
1 10
1 100
1 1000
Sample Output
9
54
384
Source
“高教社杯”第三届福建省大学生程序设计竞赛


数位DP,训练的时候也看出来了这道题是数位DP了,不过当时自己也没有做出来(太菜了)然后补了一下题目顺便学习数位DP
数位DP,也就是记忆话搜索,在数字上进行DP,比直接数数要快很多的

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;
const ll MAXN = 1e6+7;
ll dp[66][66][6],dight[66];

//长度,上一位的值,第几位(从高位往低位置数,因为题目定义就是这样子的),限制
ll dfs(int len, int pre, int id, bool limit)//
{
    
        if(len==0)       return 1;
        if(!limit&&dp[len][pre][id%2])  return dp[len][pre][id%2];

        int cnt = 0,up = (limit?dight[len]:9);

        for(int i=0;i<=up;++i)
        {
    
                if(id==1)
                {
    
                        if(i==0)        cnt += dfs(len-1,-2, id, limit&&i==up);//前导零的情况,
                        else            cnt += dfs(len-1, i, id+1, limit&&i==up);
                }
                if(id%2==0&&i>=pre)     cnt += dfs(len-1, i, id+1, limit&&i==up);//id是偶数的时候,该位置就是数字的奇数位
                if(id%2&&id!=1&&i<=pre) cnt += dfs(len-1, i, id+1, limit&&i==up);//id是奇数的时候,需要此位置小于上一位
        }

        if(!limit)      dp[len][pre][id%2] = cnt;//没有限制的话就可以记忆话了
        return cnt;
}

ll solve(ll n)
{
    
        int k = 0;
        while(n)
        {
    
                dight[++k] = n%10;
                n /= 10;
        }
        return dfs(k,-2,1,1);
}


int main()
{
    
        // freopen("../in.txt","r",stdin);
        // freopen("../out.txt","w",stdout);
        ios::sync_with_stdio(0);
        cin.tie(0);
        int t;
        cin>>t;
        while(t--)
        {
    
                ll a,b;
                cin>>a>>b;
                cout<<solve(b) - solve(a-1)<<endl;
        }
        return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Hpuer_Random/article/details/89194628

智能推荐

贝斯曲线_你被频响曲线骗了吗?-程序员宅基地

文章浏览阅读300次。烧友们在选择耳机或者其他音频设备的时候,通常都会借鉴性的参考它们的参数。比如阻抗、灵敏度、解析力、频响范围等等,他们的表现都会影响到耳机或者其他音频设备的整体素质。那么今天说的频响曲线,跟耳机的整体素质又有什么关系呢?要了解频响曲线,首先我们要知道什么是频响。频响是频率响应的简称,英文名称是Frequency Response,一般是用来描述仪器对于不同频率信号处理能力的差异。“频”指“..._频响曲线 是贝塞斯曲线吗

苹果桌面的计算机,桌面电脑远没死:苹果又重新关注它了-程序员宅基地

文章浏览阅读105次。桌面电脑回来了?其实,从技术上来说桌面电脑从来没有离开。但是在过去十年中,我们越来越多地关注移动设备:平板电脑、智能手机甚至是笔记本电脑,而在这些设备当中,苹果又占据了很大一部分的销量。但是今年我们可以轻而易举地从苹果的 WWDC 主题演讲中获取一个信息,那就是依然有很多人喜欢台式电脑。或许在有的时候,桌面电脑是没有替代品的。完整的桌面计划苹果在 WWDC 上对关于 Mac 的话题其实并没有谈论太..._苹果桌上电脑

cs5460a c语言程序,cs5460a应用电路(含源程序)-程序员宅基地

文章浏览阅读714次。描述cs5460a应用电路CS5460A主要用于智能电度表的设计,也可用于瞬时电压电流,电压电流有效值及功率的测量。电路设计可以用单片机,也可以用自引导EPROM,运用灵活可以适应不同的需求。电压电流有效值读出的是3B 24位的无符号数,而瞬时值则是有符号24位数表示,最高位表示正负。CS5460A还提供了电能计量脉冲输出端口EOUT和功率方向端口EDIR,因而可以方便的与步进电机计数器连接构成简..._cs5460a

Java命令行解析类库技术选型分析_commons cli jcommander-程序员宅基地

文章浏览阅读4.8k次。虽然在Java领域中web程序应用广泛,但是基于Java开发命令行的工具也是非常使用的,本文将介绍一下在过去几天针对命令行工具Java类库的调研结果。JCommander项目地址: https://github.com/cbeust/jcommander Star: 1010 Fork: 227 文档地址: http://jcommander.org/使用示例:p_commons cli jcommander

Spring Boot的应用启动与关闭_禁用heapdump-程序员宅基地

文章浏览阅读9.3k次,点赞2次,收藏4次。1. Spring Boot应用打包spring Boot应用可以打成jar包,其中内嵌tomcat,因此可以直接启动使用。但是在Spring Boot应用启动之前,首先需要进行打包,本文讲述的是Maven工程的打包,打包需要的前提条件(pom.xml文件中的内容)是:...jar... org.springframework.boot spring-_禁用heapdump

mysql.cant create_mysql错误:cannot create windows service for mysql.error:0-程序员宅基地

文章浏览阅读735次。安装新的MYSLQ数据库,安装好运行MySQL Server Instance ConfigWizard,在最后一步却发现无法启动服务,出现这样的提示“cannot create windows service formysql.error:0”!原因:安装mysql时可能产生cannot create windows service formysql.error:0错误,错误的原因多数由于重新安..._mysql:cant create

随便推点

SAP WM模块常用T-code_display warehouse-程序员宅基地

文章浏览阅读457次。SAP WM模块常用T-code_display warehouse

Python Tkinter 哲学家问题可视化_哲学 可视化-程序员宅基地

文章浏览阅读681次,点赞3次,收藏17次。Python Tkinter 哲学家问题可视化学校的课设总算是告一段落,现在有时间分享一下代码和心得了。这次的文章是回应之前的雏形版代码的,这次的可是完全版哦。我们先来看一下效果吧!效果总归还行吧,代码也比较简短,只有170行。再此推荐你看我之前关于这个题目的文章,接下来我直接代码讲解了。# -*- coding:utf-8 -*-#print('资源加载中,稍等片刻……')from tkinter import *from PIL import Image,ImageTk from t_哲学 可视化

LINUX服务器安全加固方法整理_检查登录提示-是否更改telnet警告banner-程序员宅基地

文章浏览阅读6.8k次,点赞5次,收藏39次。1)–设置启用空闲激活、屏幕锁定、屏保和空闲激活时间# gconftool-2 --direct \--config-source xml:readwrite:/etc/gconf/gconf.xml.mandatory \--type bool \--set /apps/gnome-screensaver/idle_activation_enabled true# gconftool-2 --direct \--config-source xml:readwrite:/etc/gconf/_检查登录提示-是否更改telnet警告banner

2. 搭建一个Spring Cloud项目_javacloud怎样集成unity-程序员宅基地

文章浏览阅读231次。搭建一个SpringCloud项目1.New Project2.聚合总父工程名字3.Maven选版本4.工程名字5.字符编码6.注解生效激活7.java编译版本选88.File Type过滤9.删除src文件夹10.修改pom.xml<?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://ww_javacloud怎样集成unity

强化学习—DQN训练计算机玩Flappy Bird游戏_paddlepaddle版flappy-bird—使用dqn算法实现游戏智能-程序员宅基地

文章浏览阅读1.1w次,点赞18次,收藏152次。文章目录Q-Learning简述Deep Q Network(DQN)为什么要用DQNDQN中的几个巧妙的地方DQN流程简述Q-Learning简述Deep Q Network(DQN)为什么要用DQNDQN中的几个巧妙的地方DQN流程简述Q Learning 就是创造一个Q表,来指导机器人的行动,Q表对应Action的数值越大,机器人就越大概率地采取这个Action.Q函数的更新方..._paddlepaddle版flappy-bird—使用dqn算法实现游戏智能

Katalon Studio简介_katalon studio的内置脚本语言是什么-程序员宅基地

文章浏览阅读1.8k次,点赞2次,收藏7次。下面是根据katalon 内置的Quick Guide截图的翻译出的基础指导:一、Katalon Studio界面功能区概观指导:二、测试用例操作手册视图指导:三、记录测试用例:四、执行与调试五、移动测试(Mobile Testing)..._katalon studio的内置脚本语言是什么