数位dp-- 数字游戏
题目

思路
也是一道比较典型的数位dp的问题,关键的思想跟我上一篇博客很像,
首先把区间值变成[1,Y]-[1,X-1]的值,然后单独计算得到结果。
总的来说就是把这个数的每一位都单独拿出来,然后根据选0-an-1和选**an**两种方案单独计算:
当选第一种方案时,就是后面的i位**(因为最低为从a0开始)的数字可以任意选,那么就可以表示为前面的最高位为last**,一共i+1位的决策数。

ps:上一篇博客的图(
那么这里求决策数就需要用到动态规划了。
这里用f[i][j]表示前面的最高位为j,并且一共有i位的不降数的集合,
那么f[i][j]肯定要从前面的状态中得到,那么在第i位为j的时候,
i-1位的选择可以为 j , j + 1 , j + 2 ,… , 9这些情况,
这些情况之和就相当于f[ i ] [ j ] , 那么f [ i ] [ j ]就可以表示为f[ i -1] [ j ]+f [ i-1 ] [ j + 1 ]+…+f [ i -1] [ 9 ]。这里可以预处理获得所有情况的f[ i ] [ j ],这样上面的方案数就可以直接算出来了(这里借用了y总的图片一用)

当选第二种方案时
即要选择当前位的最大值时,要进行特判,即上一位的最大值是不是小于当前位的最大值的,(即last<x)如果不满足则不能走到下一位直接返回,如果满足则直接进行最大值的覆盖。然后走到最右下角的决策时如果还是能选到a0,那么就作为一种方案数使res++,然后返回res即可。
具体代码
#include<cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include<vector>
#include<queue>
#include<map>
#define sc_int(x) scanf("%d", &x)
#define sc_ll(x) scanf("%lld", &x)
#define pr_ll(x) printf("%lld", x)
#define pr_ll_n(x) printf("%lld\n", x)
#define pr_int_n(x) printf("%d\n", x)
#define ll long long
using namespace std;const int N=20;
int n ,m,h;
int s[N][N];void cal()
{for(int i =0;i<=9;i++)s[1][j]=1;for(int i =1;i<=N;i++)for(int j =0;j<=9;j++)for(int k=j;k<=9;k++)s[i][j]+=s[i-1][k];
}int dp(int n)
{if(!n) return 1;//特判,如果为0也可以作为一种决策vector<int>cnt;while(n)cnt.push_back(n%10),n/=10;int res=0;int last=0;for(int i =cnt.size()-1;i>=0;i--){int x=cnt[i];for(int j =last;j<x;j++)res+=s[i+1][j];if(last>x)break;x=last;if(!i)res++;}return res;
} int main()
{int t;cal();int l,r;while(cin>>l>>r)cout<<dp(r)-dp(l-1)<<endl;return 0;
}
ps:作为数位dp的第二篇,感觉理解起来容易了很多(最不好理解的点还是方案数的预处理哪里),希望以后的数位dp能越学越熟悉吧。
相关文章:
数位dp-- 数字游戏
题目 思路 也是一道比较典型的数位dp的问题,关键的思想跟我上一篇博客很像, 首先把区间值变成[1,Y]-[1,X-1]的值,然后单独计算得到结果。 总的来说就是把这个数的每一位都单独拿出来,然后根据选0-an-1和选**an**两种方案单独计算&…...
Linux脚本 启动、重启、停止、授权
在jar包所在目录 vim start.sh | reload.sh | stop.sh输入以下命令 然后保存,进行授权 1.启动 nohup java -jar -Dfile.encodingutf-8 IntegrationFrame-sso-1.0.0-SNAPSHOT.jar & echo "started"2.重启 pid$(ps -ef|grep IntegrationFrame-sso-1.…...
Pytorch深度学习实战3-8:详解数据可视化组件TensorBoard安装与使用
目录1 什么是Tensorboard?2 Tensorboard安装3 Tensorboard可视化流程4 Tensorboard可视化实例4.1 常量可视化4.2 特征图可视化1 什么是Tensorboard? 在深度学习领域,网络内部如同黑箱,其中包含大量的连接参数,这给人工…...
华为OD机试 - 旋转骰子(C 语言解题)【独家】
最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧文章目录 使用说明本期题目:旋转骰子…...
如何做SpringBoot单元测试?
前言单元测试(unit testing),是指对项目中的最⼩可测试单元进⾏检查和验证的过程就叫单元测试,对于Java来说或者是在SpringBoot项目中,最小的可测试单元就是一个方法。做单元测试就是为了证明某段代码的执⾏结果是否符…...
ZZULI训练: 数组和字符串专题
ZZULI训练:数组和字符串专题ZZULI训练: 数组和字符串专题ZZULI训练:数组和字符串专题 部分多实例没写循环多次是因为在main里面循环了, 你们写的时候要加上只提供大概思路和核心代码建议多尝试一下c, 并没有想象的那么难 7-1 个位数统计 可以开个数组来存一下每个数组出现的…...
ElasticSearch如何解决深分页问题?
文章目录 前言From/Size参数Query阶段Fetch阶段深度分页问题Scroll遍历数据基本使用遍历优缺点缺点:优点:」Scroll Scan基本使用Scroll Scan与Scroll的区别Sliced ScrollSearch After基本使用基本原理优缺点总结ES7版本变...
JDK8新特性宝典
JDK8新特性 Java 是第一大编程语言和开发平台。它有助于企业降低成本、缩短开发周期、推动创新以及改善应用服务。如今全球有数百万开发人员运行着超过 51 亿个 Java 虚拟机,Java 仍是企业和开发人员的首选开发平台 课程内容的介绍 了解Java发展史Lambda表达式…...
【C++】关于C++模板的分离编译问题
文章目录1.阐述模板的实例化和重复定义问题2.分离编译可能出现的问题3.解决方法将函数模板的定义放到头文件中模板定义的位置显式实例化模板总结1.阐述模板的实例化和重复定义问题 C模板是一种非常强大的工具,可以为我们提供通用的代码实现方式。然鹅,在…...
小应用记账本-第2章-数据库设计
小应用记账本-第2章-数据库设计 在上一章《小应用记账本-第1章-需求分析》已经罗列了我们需要的功能,因为很简单,所以这一章就来设计数据库吧。 Account表:账户表 字段名类型说明取值idint账户idaccount_namevarchar账户名称remaining_sumd…...
Spring Boot+Vue前后端分离项目练习06之网盘项目创建vue项目
1.安装环境 构建vue项目,需要提前安装相应的环境,这里主要就是node,npm和Vue CLl。 #1、安装nodejs brew install nodejs #2、再执行下面命令来安装npm(npm是开发nodejs时所用的依赖库) brew install npm #3、安装vue cli npm install -g v…...
Python - 单元测试
python-单元测试1 Unittest2 Pytest3 两者区别断言方面用例执行编写规则前后置操作setUp, setUpclass, setUpmodule 区别4 实战操作unittest:pytest:1 Unittest unittest属于python的内置框架,支持多种自动化测试用例的编写,以及支持用例前置条件和后置…...
特权级那些事儿-实模式下分段机制首次出现的原因
前言: 操作系统的特权级模块在整个操作系统的学习中应该算的上是最难啃的了,提到特权级就要绕不开保护模式下的分段机制;如果想要彻底弄明白就要对比实模式下的分段机制有什么缺陷。这就衍生出很多问题如:什么是实模式?…...
详解Vue安装与配置(2023)
文章目录一、官网下载node.js二、安装Node.js三、环境配置四、idea导入vue项目五、IDEA添加Vue.js插件一、官网下载node.js Vue是前端开发框架。搭建框架,首先要搭建环境。搭建Vue的环境工具:node.js(JavaScript的运行环境)&…...
TypeScript深度剖析:Vue项目中应用TypeScript?
一、前言 与link类似 在VUE项目中应用typescript,我们需要引入一个库vue-property-decorator, 其是基于vue-class-component库而来,这个库vue官方推出的一个支持使用class方式来开发vue单文件组件的库 主要的功能如下: metho…...
linux面试高级篇
题目目录1.虚拟机常用有几种网络模式?请简述其工作原理或你个人的理解?2. Dockerfile中最常见的指令是什么?3.docker网络模式有哪些?4.Kubernetes有哪些核心组件这些组件负责什么工作?5. Pod是什么?6.描述一…...
java 4 (面向对象上)
java——面向对象(上) 目录java——面向对象(上)面向对象的思想概述类的成员(1-2):属性和方法对象的内存解析类中属性的使用类中方法的使用1.举例:2.声明方法:3.说明4.re…...
HTTP报头的2个方法
在采集网页信息的时候,经常需要伪造报头来实现采集脚本的有效执行 下面,我们将使用urllib2的header部分伪造报头来实现采集信息 方法1、 #!/usr/bin/python -- coding: utf-8 -- #encodingutf-8 #Filename:urllib2-header.py import urllib2 import…...
yolov5双目检测车辆识别(2023年+单目+双目+python源码+毕业设计)
行人识别yolov5和v7对比yolo车距源码:yolov5双目检测车辆识别(2023年单目双目python源码毕业设计)上盒岛APP,开线上盲盒商店http://www.hedaoapp.com/yunPC/goodsDetails?pid4132 为了提高传统遗传算法(genetic algorithm, GA)IGA优化BP网络迭代时间过长以及精度偏…...
华为OD机试题,用 Java 解【用户调度问题】问题
华为Od必看系列 华为OD机试 全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典使用说明 参加华为od机试,一定要注意不…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
