#3730. 阶梯取数最大和

阶梯取数最大和

题目描述

给定一个长度为 nn 的非负整数序列 a1,a2,…,ana_1,a_2,\dots,a_n,你需要从中选出若干个数,使得任意两个被选中的数在原序列中的下标之差至少为 22。求所有满足条件的选法中,被选中数字之和的最大值。

形式化地,选出一个下标集合 S⊆{1,2,…,n}S\subseteq\{1,2,\dots,n\},满足对任意 i,j∈Si,j\in S 且 i≠ji\ne j,都有 ∣i−j∣≥2|i-j|\ge 2,最大化 ∑i∈Sai\sum_{i\in S} a_i。

注意:可以不选任何数,此时和为 00。

输入格式

第一行一个整数 nn。

第二行 nn 个非负整数 a1,a2,…,ana_1,a_2,\dots,a_n,相邻两数用空格分隔。

输出格式

输出一行一个整数,表示满足条件的最大和。

样例

5
1 2 3 4 5 
9 
6
5 1 1 5 1 5 
15 

说明/提示

数据范围

  • 对于 30%30\% 的数据,1≤n≤201\le n\le 20。
  • 对于 60%60\% 的数据,1≤n≤10001\le n\le 1000。
  • 对于 100%100\% 的数据,1≤n≤1051\le n\le 10^5,0≤ai≤1090\le a_i\le 10^9。

提示

设 fif_i 表示只考虑前 ii 个数时能取得的最大和。若第 ii 个数不选,答案为 fi−1f_{i-1};若选第 ii 个数,则第 i−1i-1 个数不能选,答案为 fi−2+aif_{i-2}+a_i。因此 fi=max⁡(fi−1,fi−2+ai)f_i=\max(f_{i-1},f_{i-2}+a_i),边界 f0=0, f1=a1f_0=0,\ f_1=a_1。答案即 fnf_n。

解析

解题思路

题目要求选出若干下标,使任意两个被选下标之差至少为 2,并最大化选中数字之和。因为所有 aia_i 非负,所以虽然允许不选,但最优解不会因为“多选”而变差;不选只是状态转移中的一种选择。

考虑按序列顺序做决策。设 fif_i 表示只考虑前 ii 个数时能取得的最大和。

对于第 ii 个数,有两种情况:

  1. 不选第 ii 个数:答案就是前 i−1i-1 个数的最优值,即 fi−1f_{i-1}。
  2. 选第 ii 个数:由于相邻下标不能同时选,第 i−1i-1 个数一定不能选,因此前面只能从 1∼i−21\sim i-2 中选,贡献为 fi−2+aif_{i-2}+a_i。

所以状态转移方程为:

fi=max⁡(fi−1,fi−2+ai)f_i=\max(f_{i-1}, f_{i-2}+a_i)

边界为 f0=0f_0=0,f1=a1f_1=a_1。最终答案为 fnf_n。

算法选择理由

该问题具有明显的最优子结构:前 ii 个数的最优解只依赖前 i−1i-1 和前 i−2i-2 个数的最优解,且无后效性。因此直接使用一维动态规划即可,不需要枚举子集或使用复杂数据结构。

复杂度分析

  • 时间复杂度:O(n)O(n),只需一次线性扫描。
  • 空间复杂度:O(n)O(n),可优化为 O(1)O(1),但 n≤105n\le 10^5 时数组完全足够。

由于 ai≤109a_i\le 10^9,答案可能达到 101410^{14} 级别,需要使用 long long 存储。

来源

AI 生成 · 云端大模型(域):deepseek-chat · 普及+/提高- · 动态规划