【luogu CF1693D】Decinc Dividing(DP)

news/2024/3/29 22:35:33/文章来源:https://blog.csdn.net/weixin_43346722/article/details/127250722

Decinc Dividing

题目链接:luogu CF1693D

题目大意

给你一个排列,问你有多少个区间满足可以删掉一个单调递减子序列(可以是空的)得到一个单调递增数组。

思路

其实题目就是问你有多少个区间能划分成一个上升子序列和下降子序列。
首先我们考虑枚举左端点,往右扩展的时候 DP,那就是 n2n^2n2 的。
(因为有一个比较显然的性质是如果 [l,r][l,r][l,r] 不行 [l,r+1][l,r+1][l,r+1] 更加不行,所以固定左端点只有,合法的区间的右端点是一段前缀)

怎么 O(n)O(n)O(n) DP呢,一个事情就是你要用一维记录下两个序列的最后一个。
那必然有其中一个是你当前的位置,所以你只需要记录另一个位置即可。
那我们设:
fi,0f_{i,0}fi,0iii 所在的递增,递减最后一个数最大值
fi,1f_{i,1}fi,1iii 所在的递减,递增最后一个数最小值
(这个最大和最小是尽可能给后面留空间)

(其中 fi,0f_{i,0}fi,0 初始值为 −inf-infinffi,1f_{i,1}fi,1 初始值为 infinfinf,也代表无解值)
(然后初始化是 fi,0=inf,fi,1=−inff_{i,0}=inf,f_{i,1}=-inffi,0=inf,fi,1=inf

然后考虑转移,你就直接看新的数是放在哪个序列,能不能放。
考虑优化,我们试着左端点从右往左,每次新加入一个点会怎样呢?
好像不会咋样。

但是如果你 fi,0,fi,1f_{i,0},f_{i,1}fi,0,fi,1 DP 出来的结果跟之前一样,那你没必要继续下去,直接去上一轮的结果就行。
因为这个 DP 只会从 fi−1,0/1f_{i-1,0/1}fi1,0/1 来更新 fi,0/1f_{i,0/1}fi,0/1

那这个记忆化好像也没啥用。
我们试着看看每个位置的取值。
首先 inf,−infinf,-infinf,inf 都有,那我们再看会不会有别的值。
fi,0f_{i,0}fi,0 为例子,fi,1f_{i,1}fi,1 同理。

我们找到 iii 前面最大的 jjj 使得 aj>aj+1a_j>a_{j+1}aj>aj+1,那 aj,aj+1a_j,a_{j+1}aj,aj+1 不能都在递增的序列中,那就要放到递减的,又因为是最大的 jjj,所以要么是 aja_jaj 做了最后的值,要么是 aj+1a_{j+1}aj+1
那如果没有这个 jjj,那就是初始化 111 位置的 infinfinf
如果无解,就是无解的 −inf-infinf

fi,0f_{i,0}fi,0 就只有四种取值最多,fi,1f_{i,1}fi,1 也一样。
一个显然的事情是随着左端点的左移,这个值如果改变也只会单向的变化(变得更加容易无解)。
所以其实一个位置的值至多边 777 次,八种情况。

所以我们可以直接暴力从这个位置开始 DP,如果 DP 到的值跟之前的一样就直接用之前的位置作为答案进行贡献。

代码

#include<cstdio>
#include<iostream>
#define ll long long
#define INF (0x3f3f3f3f3f3f3f3f)using namespace std;const int N = 2e5 + 100;
int n, a[N], f[N][2], lst;
ll ans;
//0:i递增,递减最后一个数最大值
//1:i递减,递增最后一个数最小值 int slove(int i) {f[i][0] = INF; f[i][1] = -INF; int tmp = INF;for (int j = i + 1; j <= n; j++) {int v0 = -INF, v1 = INF;if (f[j - 1][0] != -tmp) {if (a[j] > a[j - 1]) v0 = max(v0, f[j - 1][0]);if (a[j] < f[j - 1][0]) v1 = min(v1, a[j - 1]);}if (f[j - 1][1] != tmp) {if (a[j] < a[j - 1]) v1 = min(v1, f[j - 1][1]);if (a[j] > f[j - 1][1]) v0 = max(v0, a[j - 1]);}if (v0 == f[j][0] && v1 == f[j][1]) break;f[j][0] = v0; f[j][1] = v1;if (f[j][0] == -tmp && f[j][1] == tmp) {lst = j - 1;return j - i;}}return lst - i + 1;
}int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);lst = n;for (int i = n; i >= 1; i--)ans += slove(i);printf("%lld", ans);return 0;
} 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_398904.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

软件项目管理:外包 outsourcing、采购 procurement、合同 contracts

文章目录外包不同类型为什么选择外包好处坏处采购 procurementplanning 阶段-弄清需求 & 市场 / 评估风险Source 阶段-确定供应商具体过程RFxState of Work (SOW)评估步骤 Evaluation processManage 阶段Contract 合同定义种类固定价格合同适用场景&#xff08;保守&#x…

稀疏矩阵的压缩存储

目录 稀疏矩阵的定义 稀疏矩阵的转置 代码实现 运行结果 稀疏矩阵的定义 假设在 m * n 的矩阵中&#xff0c;有 t 个元素不为零&#xff0c;且 t<<m*n&#xff0c;则称此矩阵为稀疏矩阵。按照常规的存储方法&#xff0c;稀疏矩阵很浪费内存空间&#xff0c;所以采取…

学习梦想家CMS内容管理系统-环境启动

gitee官网中项目的地址&#xff1a;首先准备里面提到的工具其中JDK8和MySQL5.7我们已经有了&#xff0c;现在需要准备另外的工具。 Spring Tool Suite 4&#xff08;STS&#xff09; 安装过程在《1-1-Spring Tool Suite 4&#xff08;STS&#xff09;的下载安装》 Redis 安装…

数字孪生在电网系统开发建设,如何选择可视化平台?

随着新能源发展规模持续增大&#xff0c;电网作为能源转换利用和输送配置的枢纽平台&#xff0c;其功能、结构和形态发生了深刻变化。同时&#xff0c;随着现代计算机技术发展&#xff0c;数字孪生成为电网向数字化转型、提高电网调度运行决策的准确性与实时性提供关键技术支撑…

初识数据库-MySQL数据库

文章目录数据库数据库的相关概念常见的关系型数据库管理系统MySQL数据库MySQL目录结构MySQL数据模型数据库 数据库的相关概念 数据库 存储数据的仓库&#xff0c;数据是有组织的进行存储英文&#xff1a; DataBase,简称 DB 数据库管理系统 管理数据库的大型软件英文&#xff…

震撼上新丨云和恩墨新一代数据库存储 zStorage 和数据库一体机 zData X 即将发布...

存储&#xff0c;在一定程度上可以称为数据库存储&#xff0c;存储与数据库的发展总是相生相随。技术上&#xff0c;数据库对高 I/O 频率、低时延、高可靠性的追求一直是存储更快、更高、更强需求的来源。商业上&#xff0c;两家影响世界的公司 Oracle 和 EMC 几乎同时起步于 1…

使用element ui的el-upload组件上传图片,记录一下

使用element ui的el-upload组件上传图片 效果预览 下面是实现效果,接口方面是把有两个接口,一个接口上传图片,传参是图片和路径,返回值是路径。另一个接口是上传表单内容(用户,地址,照片),照片是传一个路径。具体实现 html <el-form-item label="上传照片"…

第二十一章 函数递归

一、函数递归调用介绍 函数不仅可以嵌套定义,还可以嵌套调用,即在调用一个函数的过程中,函数内部又调用另一个函数,而函数的递归调用指的是在调用一个函数的过程中又直接或间接地调用该函数本身。例如在调用f1的过程中,又调用f1,这就是直接调用函数f1本身def f1():print(…

springboot(三)

视频链接&#xff1a;https://www.bilibili.com/video/BV1XQ4y1m7ex/?vd_source9545770e4a2968c05878ffac8589ec6c 视频选集&#xff1a;P58— P92 文章目录1.接口架构风格-RESTful1.1 认识REST1.2 RESTful的注解1.2.1 PathVariable1.2.2 PostMapping1.2.3 DeleteMapping1.2.4…

分布式缓存

本文介绍关于缓存的常用设计模式。以及如何保证缓存的一致性进行分类讨论。 还会介绍关于缓存失效的常见问题&#xff0c;以及针对缓存失效的解决方法。 在高并发的环境下&#xff0c;比如春节抢票大战&#xff0c;一到放票的时间节点&#xff0c;分分钟大量用户以及黄牛的各种…

魔改xxl-job,彻底告别手动配置任务!

xxl-job是一款非常优秀的任务调度中间件,轻量级、使用简单,但是苦于手动注册任务久矣,今天就来魔改一下,实现任务的自动注册!原创:微信公众号 码农参上,欢迎分享,转载请保留出处。哈喽大家好啊,我是Hydra。 xxl-job是一款非常优秀的任务调度中间件,轻量级、使用简单、…

12个小细节让普源示波器使用更加高效(上)

俗话说细节决定成败&#xff0c;示波器作为电子测量的第一工具&#xff0c;虽然使用简单&#xff0c;但并不是每个人都能注意到细节。运用好细节&#xff0c;可以使你的示波器使用更加的便捷。以下由安泰测试带来普源示波器测量相关的12个小细节可作为示波器常识快速自检的小文…

Spring Boot(4):@Import注解和@Conditional注解

说明&#xff1a;基于atguigu学习笔记。 在了解spring boot自动配置原理前&#xff0c;再来了解下两个注解Import注解和Conditional注解。 Import Import注解主要用于导入某些特殊的Bean&#xff0c;这些特殊的Bean和Bean Definitaion 有关。 主要用于导入Configuration 类…

Python实现桌面挂件,做一只可爱的桌面宠物~

文章目录嗨嗨&#xff0c;大家好 ~ 我是小圆相关文件开发工具相关模块&#xff1a;环境搭建安装原理简介1.初始化一个窗口组件&#xff1a;效果2.设置一下窗口的属性&#xff1a;随机导入一张图片&#xff0c;看效果随机导入一个宠物的所有图片的函数代码3.宠物随机出现在桌面上…

服务端渲染的探索与实践

服务端渲染(SSR)近两年炒得很火热,相信各位同学对这个名词多少有所耳闻。本节我们将围绕“是什么”(服务端渲染的运行机制)、“为什么”(服务端渲染解决了什么性能问题 )、“怎么做”(服务端渲染的应用实例与使用场景)这三个点,对服务端渲染进行探索。 服务端渲染是一…

GOM引擎登录器的研究,逆向技术在这款GOM20151108引擎上是一个大舞台

最近遇到一个逆向类课题&#xff0c;是关于GOM20151108版本对应登录器研究。刚接触传奇的时候是2002年&#xff0c;那时候网吧玩SF&#xff0c;都是手动用IP直接连接&#xff0c;当时的一款 联创传奇 很好玩&#xff0c;有传送戒子&#xff0c;木域戒指&#xff0c;土域戒指&am…

不会 Vue,但不影响我学 diff 算法

前言 现在社会各行各业大都面临着寒冬&#xff0c;互联网行业最近还出现了裁员潮&#xff0c;导致前端是越来越卷&#xff0c;普通学校的应届生不仅要跟985、211毕业的学生以及研究生进行竞争&#xff0c;甚至还需要和最近刚被裁的、有了几年工作经验的程序员竞争&#xff0c;…

page.json

uni-app需要给page.json文件需要进行配置路由,否则会不报错,也跳转不过去

【数模/启发式算法】蚁群算法

文章目录简介符号说明核心思想流程图文章使用到的测试函数基本步骤蚁群算法代码简介 蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出&#xff0c;其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 这种算法具有分布计算、信息正…

Arduino播放声音

玩软件有点虚无&#xff0c;没有实际东西&#xff0c;所以接下来要体验下硬件与软件结合。 1 Arduino Arduino是一种包含硬件&#xff08;各种型号的Arduino板&#xff09;和软件&#xff08;Arduino IDE&#xff09;的开源电子平台。硬件部分是可以用来做电路连接的Arduino电…