数位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机试,一定要注意不…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态
前言 在人工智能技术飞速发展的今天,深度学习与大模型技术已成为推动行业变革的核心驱动力,而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心,系统性地呈现了两部深度技术著作的精华:…...
前端工具库lodash与lodash-es区别详解
lodash 和 lodash-es 是同一工具库的两个不同版本,核心功能完全一致,主要区别在于模块化格式和优化方式,适合不同的开发环境。以下是详细对比: 1. 模块化格式 lodash 使用 CommonJS 模块格式(require/module.exports&a…...
