当前位置: 首页 > news >正文

蓝桥杯22年第十三届省赛-数组切分|线性DP

题目链接:

蓝桥杯2022年第十三届省赛真题-数组切分 - C语言网 (dotcpp.com)

 1.数组切分 - 蓝桥云课 (lanqiao.cn)

这道题C语言网数据会强一些。 

 说明:

对于一个切分的子数组,由于数组是1-N的一个排列,所以每个数唯一 可以用子数组最大值-最小值==子数组长度-1(子数组右端点索引 -左端点索引+1-1)来判断 。
  
 尝试题目求什么,我们就设dp数组为 什么,那么设f[i]为 前i个数能有f[i]种方案, 
 观察样例,手工计算, A=1,3,2,4 
 i为1时,方案为 : 
 {1} 
 i为2时,方案为: 
  {1}{3}    而{1,3}不行   
 i为3时,方案为 :
 {1}{3}{2},{1}{3,2},{1,3,2} 而{1,3}{2}不行   
 i为4时,方案为:
  {1}{3}{2}{4},{1}{3,2}{4},{1,3,2}{4} ,{1}{3,2,4},{1,3,2,4} 
  而{1}{3}{2,4},{1,3}{2}{4}不行 
  
  发现当加入第i个数是时,如果把第j个数和第i个数划成一组,如果这个划分合法,
  那么他就能和f[j-1] 的每个方案 组合成 合法方案,于是累加上[j,i]划分合法时每个
  f[j-1]就是f[i]的值 。


 注意:如果1到i所有数在一个切分里能组成合法的区间,这时的j-1为0 ,故初始化f[0]=1

在c语言网用scanf输入,才能ac,用cin有一个测试点过不了。

代码:

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;/*对于一个切分的子数组,由于数组是1-N的一个排列,所以每个数唯一可以用子数组最大值-最小值==子数组长度-1(子数组右端点索引-左端点索引+1-1)来判断 尝试题目求什么,我们就设dp数组为 什么,那么设f[i]为 前i个数能有f[i]种方案, 观察样例,手工计算, A=1,3,2,4 i为1时,方案为 : {1} i为2时,方案为: {1}{3}    而{1,3}不行   i为3时,方案为 :{1}{3}{2},{1}{3,2},{1,3,2} 而{1,3}{2}不行   i为4时,方案为:{1}{3}{2}{4},{1}{3,2}{4},{1,3,2}{4} ,{1}{3,2,4},{1,3,2,4} 而{1}{3}{2,4},{1,3}{2}{4}不行 发现当加入第i个数是时,如果把第j个数和第i个数划成一组,如果这个划分合法,那么他就能和f[j-1] 的每个方案 组合成 合法方案,于是累加上[j,i]划分合法时每个f[j-1]就是f[i]的值 。注意:如果1到i所有数在一个切分里能组成合法的区间,这时的j-1为0 ,故初始化f[0]=1*/int a[N]; 
//表示前i个数能有f[i]种切分方法 
int f[N]; 
int mod=1000000007;
int n;
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++){//	cin>>a[i];//开long long 之后 用scanf格式控制符要用lld//用scanf要关掉上面的ios语句 scanf("%d",&a[i]); }//需要初始化0处为1,因为如果1到i所有数在一个切分里能组成合法的区间//这时的j-1为0 ,故f[0]=1f[0]=1;f[1]=1;for(int i=2;i<=n;i++){//序列最小值减最大值等于序列长度-1,即为自然数 int ma=a[i],mi=a[i];for(int j=i;j>=1;j--){//维护最值 ma=max(ma,a[j]),mi=min(mi,a[j]);if(ma-mi==i-j){f[i]=(f[i]+f[j-1])%mod;}}}cout<<f[n];return 0;
}

相关文章:

蓝桥杯22年第十三届省赛-数组切分|线性DP

题目链接&#xff1a; 蓝桥杯2022年第十三届省赛真题-数组切分 - C语言网 (dotcpp.com) 1.数组切分 - 蓝桥云课 (lanqiao.cn) 这道题C语言网数据会强一些。 说明&#xff1a; 对于一个切分的子数组&#xff0c;由于数组是1-N的一个排列&#xff0c;所以每个数唯一 可以用子…...

小米汽车:搅动市场的鲶鱼or价格战砧板上的鱼肉?

3月28日晚&#xff0c;备受关注的小米汽车上市发布会召开&#xff0c;小米集团董事长雷军宣布小米SU7正式发布。小米汽车在带飞股价的同时&#xff0c;二轮订购迅速售尽。 图一&#xff1a;小米集团股价 雷军口中“小米汽车迈出的第一步&#xff0c;也是人生最后一战的开篇”&a…...

Docker 学习笔记(五):梳理 Docker 镜像知识,附带 Commit 方式提交镜像副本,安装可视化面板 portainer

一、前言 记录时间 [2024-4-10] 前置文章&#xff1a; Docker学习笔记&#xff08;一&#xff09;&#xff1a;入门篇&#xff0c;Docker概述、基本组成等&#xff0c;对Docker有一个初步的认识 Docker学习笔记&#xff08;二&#xff09;&#xff1a;在Linux中部署Docker&…...

K8S node节点执行kubectl get pods报错

第一个问题是由第二个问题产生的&#xff0c;第二个问题也是最常见的 网上找的都是从master节点把文件复制过来&#xff0c;这样确实可以解决&#xff0c;但是麻烦&#xff0c;有一个node节点还好&#xff0c;如果有多个呢&#xff1f;每个都复制吗&#xff1f;下面是我从外网…...

C++简单日志系统

需求描述 日志等级&#xff1a;定义一个枚举类型 LogLevel&#xff0c;包含至少四个等级&#xff1a;DEBUG、INFO、WARNING、ERROR。日志记录&#xff1a;实现一个 Logger 类&#xff0c;包含以下功能&#xff1a; 一个静态方法 log&#xff0c;接受 LogLevel 和一个字符串作为…...

MySQL基础练习题:习题21-25

这部分主要是为了帮助大家回忆回忆MySQL的基本语法&#xff0c;数据库来自于MySQL的官方简化版&#xff0c;题目也是网上非常流行的35题。这些基础习题基本可以涵盖面试中需要现场写SQL的问题。 列出在部门sales工作的员工的姓名&#xff0c;假定不知道销售部的部门编号 sele…...

全面的网络流量监控

流量监控指的是对数据流进行的监控&#xff0c;通常包括出数据、入数据的速度、总流量。通过网络流量监控&#xff0c;组织可以确保只有业务关键型流量通过网络传输&#xff0c;并限制不需要的网络流量&#xff0c;从而提高网络效率&#xff0c;又可以防止停机、减少 MTTR、帮助…...

探索网络爬虫:技术演进与学习之路

网络爬虫及IP代理池 前言爬虫技术的演进最新的爬虫技术爬虫技术学习路线 前言 在信息时代&#xff0c;网络爬虫技术作为获取和处理网络数据的重要手段&#xff0c;已经成为数据科学、机器学习和许多商业应用的基石。从简单的HTML页面抓取到复杂的动态内容采集&#xff0c;爬虫…...

目标检测——色素性皮肤病数据集

一、重要性及意义 首先&#xff0c;色素性皮肤病变是一类常见的皮肤疾病&#xff0c;其发病率有逐年增高的趋势。这些病变可能由遗传或环境因素导致黑素细胞生成异常&#xff0c;如黑色素瘤等。黑色素瘤具有极高的恶性率和致死率&#xff0c;而且恶化可能性大&#xff0c;容易…...

Unity3D 打空包与远程资源更新详解

前言 在游戏开发过程中&#xff0c;打包和远程资源更新是非常重要的步骤&#xff0c;本文将详细介绍Unity3D中如何进行打空包和远程资源更新。 对惹&#xff0c;这里有一个游戏开发交流小组&#xff0c;希望大家可以点击进来一起交流一下开发经验呀&#xff01; 一、打空包 …...

32单片机入门持续更新中

配套资料为野火霸道V2 初识 STM32 4.1 什么是 STM32 STM32&#xff0c;从字面上来理解&#xff0c;ST 是意法半导体&#xff0c;M 是 Microelectronics 的缩写&#xff0c;32 表示 32 位&#xff0c;合起 来理解&#xff0c;STM32 就是指 ST 公司开发的 32 位微控制器。在如今…...

蓝桥杯 每天2题 day6

碎碎念&#xff1a;哇咔咔 要不是中间缺勤一天就圆满day7了&#xff01;最后一晚上&#xff01;写题复习哇咔咔 唉&#xff0c;睡了一觉就看不下去了&#xff0c;&#xff0c;&#xff0c;看看之前的笔记洗洗睡觉&#xff0c;&#xff0c;&#xff0c; 记得打印准考证带好东西…...

Fast-lio2运行时如何显示轨迹线

修改对应设备的.yaml文件&#xff0c;以velodyne为例&#xff1a; 将 path_en参数改为true即可&#xff0c;运行其他设备&#xff0c;修改对应的参数...

2022年全国青少年信息素养大赛Python国赛第1-10题,含解析答案

01-分苹果 把一堆苹果分给n个小朋友,每个人拿到的苹果数量不同,并且每个人至少有一个。任意输入小朋友的数量n,问这堆苹果至少应该有多少个。输入描述:任意输入小朋友的数量n输出描述:输出这堆苹果至少应该有多少个 样例输入: 3 样例输出: 6 注意: input()内不添…...

python学习笔记——文件操作

1. 文件操作**** 1.1. open()函数**** 参数&#xff1a; 1. File&#xff1a;需要打开的文件 2. Mode&#xff1a;读、写、读写 (1) r&#xff1a;只读 (2) w&#xff1a;只写文件&#xff08;覆盖&#xff09; (3) a&#xff1a;只写文件&#xff08;追加&#xff09; …...

滑动窗口用法

文章目录 1. 长度最小的子数组&#xff08;模板&#xff09;2. 无重复字符的最长字串3. 最小覆盖字串4. 加油站5. 替换字串得到平衡字符串 1. 长度最小的子数组&#xff08;模板&#xff09; 题目分析 直接用步骤分析示例1&#xff0c;[]表示窗口&#xff0c;min_length表示满…...

智慧港口整体解决方案(一)

前言 智慧港口建设对创新驱动、转型发展具有重要推动作用加快推动第五代港口发展进程,成为当今港口转变发展方式、 提升企业综合竞争力的主潮流。智慧港口是港口未来发展主要方向 物联网、云计算技术发展智慧港口是物联网、移动互联网、云计算、人工智能等高新 技术与港口功能的…...

ubuntu如何限制系统日志大小?

ubuntu中的系统日志文件件如不及时清理&#xff0c;时间长了会占用硬盘的空间&#xff0c;如下所示&#xff1a; /var/log/journal/4321d62ad63d44cbbc4dff3b6e282b26/system9f5b4d5081d24b319f8b4677cf673a97-0000000000184ca6-00061412655a5a79.journal: 128M /var/log/journ…...

【Linux】线程概念及线程互斥

目录 线程概念 线程优点 线程缺点 线程异常 线程系统编程接口 线程创建及终止 线程等待 使用线程系统接口封装一个小型的C线程库并实现一个抢票逻辑 线程互斥 互斥量的接口 线程互斥实现原理 使用系统加锁接口封装LockGuard 实现自动化加锁 线程安全和可重入函数 …...

测试需求分析

测试需求是什么&#xff1f; --需求文档 测试需求主要解决**“测什么”的问题&#xff0c;一般来自需求规格说明书中原始需求 测试需求应全部覆盖已定义的业务流程&#xff0c;以及功能和非功能**方面的需求 功能&#xff1a;基本用户需求–优先 非功能&#xff1a;界面&#…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...