【GESP】2026年3月C++ 六级真题解析,luogu-P15800 选数 | 六级典型门槛题

四季读书网 2026-03-27 14:58:13 1 0

科普类资源清单
🤞信奥业余科普

GESP学习资源清单

真题	练习题	考纲解析
一级真题清单	一级练习题清单	111-8级全考纲解析
二级真题清单	二级练习题清单	GESP/CSP必备技能
三级真题清单	三级练习题清单	考纲解密
四级真题清单	四级练习题清单	资源汇总/经验交流
五级真题清单	五级练习题清单
六级真题清单	六级练习题清单

CSP学习资源清单

CSP-XL‍	CSP-J
2025辽宁CSP-XL复赛真题解析	CSP-J 真题解析

NOI学习资源清单

NOIP
1998年真题解析‍‍
1999年真题解析
*2001年真题解析‍‍*
2011年真题解析

2026年3月，GESP六级真题，考察线性动态规划，难度⭐⭐⭐☆☆。洛谷难度等级：普及/提高−。

P15800 [GESP202603 六级] 选数

题目要求

题目描述

给定两个包含个整数的数组与。你需要指定若干下标（）使得以下条件成立：

（）；
（）。

你需要在满足以上条件的前提下最大化，也即最大化数组对应下标的整数之和。

（注：题目原描述中应为笔误，根据题意及输入输出样例，实际为求和）

输入格式

第一行，一个正整数，表示数组长度。

第二行，个正整数，表示数组。

第三行，个正整数，表示数组。

输出格式

一行，一个整数，表示在满足下标条件的前提下，数组对应下标的整数之和的最大值。

输入输出样例 #1

输入 #1

41 2 3 43 3 1 1

输出 #1

输入输出样例 #2

输入 #2

61 1 4 5 1 41 2 3 2 1 0

输出 #2

说明/提示

对于的测试点，保证。

对于所有测试点，保证，，。

题目分析

这道题考察了动态规划（DP）的思想。题目要求我们在数组中选择若干个元素，使得它们的和最大，并且如果选择了下标为的元素，下一个选择的元素下标必须满足，且由于序列必须递增，同时显然还要满足。

状态定义：定义 dp[i] 为在后缀数组中进行选择，所能得到的最大和。
状态转移方程：对于第个元素，我们有两种选择：
综合上述两种情况，状态转移方程为：

不选第个元素：那么最大和就是从到中选择的最大和，即 dp[i+1]。
选第个元素：那么我们获得了的价值，下一个能选的元素下标必须至少是。那么从这个合法的下一个位置到的最大和就是 dp[next_idx]，其中 next_idx = max(i + 1, i + b[i])。

初始状态与遍历顺序：由于计算 dp[i] 时需要用到它后面的状态 dp[i+1] 以及 dp[next_idx]，我们需要从后往前逆序遍历（即从到）。超出数组范围的 dp[n+1] 等初始化为。
数据范围注意：题目给出，。如果全选，最大和可能达到，超过了 32 位有符号整数 int 的表示范围（最大约），因此 dp 数组必须使用 long long 类型。

示例代码

#include<iostream>#include<vector>#include<algorithm>// 使用 long long 防止累加结果溢出typedef long long ll;const int MAXN = 100005;ll a[MAXN];int b[MAXN];ll dp[MAXN * 2]; // 稍微开大一点防止越界intmain(){    // 优化输入输出速度    std::ios_base::sync_with_stdio(false);    std::cin.tie(NULL);    int n;    std::cin >> n;    for (int i = 1; i <= n; i++) {        std::cin >> a[i];    }    for (int i = 1; i <= n; i++) {        std::cin >> b[i];    }    // 从后往前计算 DP    // dp 数组默认全为 0，dp[n+1] 开始往后都是 0，作为边界条件    for (int i = n; i >= 1; i--) {        // 下一个可以选择的位置        // 注意：除了满足题目给出的 i + b[i]，还必须严格大于当前位置 i        int next_idx = std::max(i + 1, i + b[i]);        if (next_idx > n + 1) {            next_idx = n + 1; // 越界部分当作 n + 1 处理，对应 dp 值为 0        }        // 状态转移：取“不选当前元素”和“选当前元素”的最大值        dp[i] = std::max(dp[i + 1], a[i] + dp[next_idx]);    }    // dp[1] 即为在整个数组 1...n 中选择的最大和    std::cout << dp[1] << "\n";    return 0;}

代码解析小贴士

逆向思维：很多序列选择类的动态规划题目，如果从前往后定义状态比较复杂（因为要记录上一个选了什么，可能会导致状态维数增加或者转移过程很绕），可以尝试从后往前定义 dp[i] 表示“从开始到末尾的最大价值”，这样状态转移只依赖后面的结果，逻辑会清晰得多。
数据类型溢出：在 GESP 考级或信奥赛中，看到数值范围，基本可以判定累加和会超过 int 上限，果断开 long long 是避免只拿部分分的好习惯。