#P17820. [Ontak2022]ANT
[Ontak2022]ANT
题目描述
给定一个长度为 的序列。第 个元素有数值 和权重 。
一个非空序列 称为循环交替序列,当且仅当 为偶数,并且将下标对 取模后,每个元素都是严格的局部极大值或严格的局部极小值,二者交替出现。也就是说,相邻元素不能相等,且
$$b_{i-1}<b_i\Longrightarrow b_i>b_{i+1},\qquad b_{i-1}>b_i\Longrightarrow b_i<b_{i+1}.$$特别地,首尾相邻处也必须满足上述条件。长度为 且两元素不同的序列合法。
从原序列中选出一个不必连续的子序列,保持下标递增,使其数值构成循环交替序列,并使所选元素的权重和最大。
输入格式
第一行一个整数 。第二行 个整数 。第三行 个整数 。
输出格式
输出最大权重和;如果不存在合法的非空子序列,输出 NO。答案可以为负数。
数据范围
,,。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | N≤20 | 5 |
| 2 | N≤500 | 11 |
| 3 | N≤10000 | 27 |
| 4 | 所有 wᵢ=1 | 17 |
| 5 | 所有 aᵢ≤20 | 21 |
| 6 | 无额外限制 | 19 |
样例 1
输入:
9
6 2 6 3 8 3 10 1 4
1 1 1 1 -1 -1 1 1 1
输出:
6
说明
样例的一种最优子序列为 (6,2,6,3,10,4),权重和为6;只满足线性交替但首尾不闭合的子序列不合法。