编程题
P15800 选数
【题目来源】
洛谷：[P15800 GESP202603 六级] 选数 - 洛谷
【题目描述】
给定两个包含 \(n\) 个整数的数组 \(a=[a_1,\dots,a_n]\) 与 \(b=[b_1,\dots,b_n]\)。你需要指定若干下标 \(p_1\lt \cdots\lt p_k\)（\(1\leq k\leq n\)）使得以下条件成立：
- \(1\leq p_i\leq n\)（\(1\leq i\leq k\)）；
- \(p_{i+1}\geq p_i+b_{p_i}\)（\(1\leq i< k\)）。
你需要在满足以上条件的前提下最大化 \(\sum_{i=1}^k a_{p_k}\)，也即最大化数组 \(a\) 对应下标的整数之和。
【输入】
第一行，一个正整数 \(n\)，表示数组长度。
第二行，\(n\) 个正整数 \(a_1,a_2,\dots,a_n\)，表示数组 \(a\)。
第三行，\(n\) 个正整数 \(b_1,b_2,\dots,b_n\)，表示数组 \(b\)。
【输出】
一行，一个整数，表示在满足下标条件的前提下，数组 \(a\) 对应下标的整数之和的最大值。
【输入样例】
4
1 2 3 4
3 3 1 1
【输出样例】
7
【算法标签】
《洛谷 P15800 选数》 #动态规划DP# #GESP# #2026#
【代码详解】
// 40分版本
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100005;int n, a[N], b[N], ans;
// dp[i] 表示以第 i 个活动结尾时，能获得的最大价值
int dp[N];
int len = 0;signed main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= n; i++){cin >> b[i];}for (int i = 1; i <= n; i++){// 初始化：只选择第 i 个活动dp[i] = a[i];// 考虑在 i 之前的活动 jfor (int j = 1; j < i; j++){// 检查活动 j 结束后是否可以安排活动 iif (i >= j + b[j]){// 如果可以，则尝试从活动 j 转移到活动 idp[i] = max(dp[i], dp[j] + a[i]);}}}// 找到所有 dp[i] 中的最大值for (int i = 1; i <= n; i++){ans = max(ans, dp[i]);}cout << ans << endl;return 0;
}
// 100分版本
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100005;int n, a[N], b[N];
// dp[i]: 到时间i为止能获得的最大收益（不包含在时间i开始的任务）
int dp[N];signed main()
{ cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= n; i++){cin >> b[i];}int ans = 0;for (int i = 1; i <= n; i++){// 情况1: 在时间i开始执行任务i// 收益 = 到时间i为止的最大收益 + 任务i的收益ans = max(ans, dp[i] + a[i]);// 如果执行任务iint finish_time = i + b[i];if (finish_time <= n){// 在任务i结束时更新收益dp[finish_time] = max(dp[finish_time], dp[i] + a[i]);}// 情况2: 在时间i不执行任何任务// 收益延续到下一个时间点dp[i + 1] = max(dp[i + 1], dp[i]);}// 注意：最终答案不一定是dp[n]，因为可能在n时刻之前就已经得到了最大收益// 我们已经在循环中通过ans记录了所有可能的最大值cout << ans << endl;return 0;
}
【运行结果】
4
1 2 3 4
3 3 1 1
7