P2501 [HAOI2006] 数字序列

news/发布时间2024/6/17 20:47:38

先来看第一问。

发现直接做要考虑两数中间的数能否变得合法,所以按套路将 \(a_i\) 减去 \(i\),这样就只要变成单调不降,只要两数合法中间的数就一定能变得合法。考虑不改变的那些数,它们一定单调不降,所以答案就是序列总长度减去最长不下降子序列的长度。

接下来看第二问,尝试观察一些性质:

  • 可能有多个最长不下降子序列,每个子序列的答案都有可能成为最小值。
  • 子序列中相邻的两项之间的任意一个数要么不小于前一项,要么不大于后一项,否则将其并入子序列长度会更长。

现在我们有两个相邻的数,都需要修改,前者大于后者。显然,将它们修改成两数之间的任意一个数代价都是最小的。应用到子序列的相邻两项 \(i\)\(j\) 之间,假设某种情况第 \(k\) 个数修改成了 \(b_k\),将相同数合并,那么我们就得到了一个新的序列 \(b\)。考虑其中相邻的三项 \(x,y,z(i\leq x<x+1=y<y+1=z\leq j,b_x<b_y<b_z)\),我们将 \(b_y\) 修改成 \(b_x\)\(b_z\),要么代价都不变,要么有一种代价会减小。按这样一直搞下去最终只会剩下 \(i\)\(j\) 这两项,所以我们就得到了一个结论:最优解一定存在一个断点 \(k\),使得 \(b_i=b_k<b_{k+1}=b_j\)

然后用这个结论直接暴力就行了,时间复杂度 \(O(n\log a+n^3)\),但因为数据是随机的所以根本跑不满。

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

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

相关文章

LVS+Keepalived群集

LVS+Keepalived群集 Keepalived是一个基于VRRP协议来实现的LVS服务高可用方案,可以解决静态路由出现的单点故障问题。 在一个LVS服务集群中通常有主服务器(MASTER)和备份服务器(BACKUP)两种角色的服务器,但是对外表现为一个虚拟IP(VIP),主服务器会发送VRRP通告信息给备…

python实现从网站下载文件, 带进度信息

我实现了一个函数, 代码如下: def download_file_from_url(url, save_path=, callback:callable = None):下载文件, 并保存到save_path指定的位置url: 形如http://www.tdx.com.cn/products/data/data/vipdoc/shlday.zip 或者http://www.tdx.com.cn/products/data/data/vipdoc/s…

P2759 奇怪的函数

71923232_p6不学不知道,做过初升高暑假作业就会了。 \[\large x=10^{\log_{10}^x} \]\[\large x^x=\left(10^{\log_{10}^x}\right)^x=10^{x\log_{10}^x} \]因为是达到或超过,所以指数下取整加一即是位数。 然而 \(x\) 的范围比较大,直接枚举不行,要二分。

RocketMQ 入门实战(4)--Java 操作 RocketMQ

本文主要介绍使用 Java 来操作 RocketMQ,文中所使用到的软件版本:Java 1.8.0_341、RocketMQ 5.1.3、rocketmq-client-java 5.0.5。 1、引入依赖<dependency><groupId>org.apache.rocketmq</groupId><artifactId>rocketmq-client-java</artifactId…