10.20模拟赛 序列

题意

给出长度为 \(n\) 的序列 , 对所有 \(K\in[1,N]\) 求出长度为 \(K\) 的子序列的权值最大值。

\(1 \leq n \leq 2\times10^5\)

解法

这个东西是长得比较奇怪的 \((max,+)\) 卷积。考虑怎么优化。

对于 \(O(n^2)\) 就维护 \(f(i,j)\) 表示目前处理到序列的第 \(i\) 个元素,子序列长度为 \(j\) 的权值最大值。然后我们一个一个向内部加入元素,转移就是 \(f(i,j) = \max \{f(i-1,j),f(i-1,j-1) ±a_i\}\)

这个暴力就是普通的 \((max,+)\) 卷积。总质量和单个物品质量没有什么特殊性质,接下来只剩下凸性这条路径了。

接下来,我们将证明 \(K\) 的奇偶分开后,在 \(i\) 固定的情况下 \(f(i,K)\) 是满足凸性的。

这里只证明偶数的情况,奇数的情况可以以此类推。

因为这里是偶数间的转移,所以我们加入物品可以视作两个两个加入。

我们将 \(f(i,K)\) 的选择序列进行划分。

假设原选择序列为

\[A_{i_1},A_{i_2},A_{i_3},A_{i_4},…,A_{i_{k-1}},A_{i_k} \]

偶数位置贡献为负数,奇数位置贡献为正数。我们插入两个元素\(A_l,A_r\),即加上 \(A_l – A_r\) 然后将 \((l,r)\) 内的所有元素取个反。

把贡献拆开来,变成取反 \([1,r]\) 然后取反 \([1,l]\).

设目前填的序列中 \(g(x)\)\([1,x]\) 的贡献。

那么贡献即为 \(A_l + g(l) – A_r – g(r)\). 我们每次选择最大权值的 \(l\) 和最小权值的 \(r\) 即可。

接着我们只需证明对于 \(g(l) – g(r) (1\leq l \leq r \leq n)\) 具有单调递减的性质,即可得知每次新的贡献与整个 \(f\) 同样具有凸性。

我们发现当贡献产生在 l 左侧或 r 右侧时,该值不变。
当贡献产生在中间时才能产生贡献。
设产生影响的点为 \(j\)
那么 \((l,j)\) 间的取反才会产生贡献。若 \((l,j)\) 间的取反产生的贡献为正。那么对于先前的决策而言,加入 \((l,r)\) 并没有加入 \((l,j)\) 优秀。

因此我们取反产生的 \(( g(l) – g(r) )\) 总为负数。凸性得证

知道了凸性,我们考虑利用这个性质。

然后我们进一步分析转移。

我们先写出较为暴力的形式

其中 \(f(x),g(x)\) 表示长度为 \(x\) 的子序列的权值最大值和最小值

考虑如何合并左右两个区间

\[\left\{\begin{matrix} f'(K) = \max\{\max_{i+j=k,\text{i is odd} }\{ f_l(i) – g_r(j)\} , \max_{i+j=k,\text{i is even} }\{ f_l(i) + f_r(j)\}\}\\ g'(K) = \min\{\min_{i+j=k,\text{i is odd} }\{ g_l(i) – f_r(j)\} , \min_{i+j=k,\text{i is even} }\{ g_l(i) + g_r(j)\}\} \end{matrix}\right. \]

由于这个是凸的,因此差分数组单调,使用two pointer即可优化合并凸壳至线性。
利用合并线性的性质,我们结合分治,就可以做到 \(O(nlogn)\) 的优质复杂度。

代码

原文地址:http://www.cnblogs.com/Hencecho/p/16813482.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性