P1018小核桃与数组规则 普及- CSP-J组 排序 线性DP 标准IO 传统题 来源 TomAnderson 时间限制 1000ms 内存限制 256MB 通过/尝试次数 2225/2901 题目描述 小核桃身处在一个神秘的逃生游戏中，他需要通过解决各种谜题来获得能够帮助他逃脱的物品。在一道谜题中，小核桃被赋予了一个整数数组和一组规则，让他按顺序进行操作。以下是给小核桃的指示：给定一个整数数组，请按以下方法计算得分最高的方案： 首先选择一个整数 v v 并删除数组中所有等于 v v 的元素，并将它们的总和加入积分中。 同时，删除数组中所有等于 v + 1 v+1 或 v − 1 v−1 的元素，这些元素不得分。 重复上述步骤，直到数组中没有更多的元素为止。 现在，小核桃需要计算按照这些规则可以获得的最大分数是多少？ 输入描述 第一行包含一个整数 n n,表示有 n n 个整数。 第二行包含 n n 个整数，表示第 i i 个数字值为 a i a i ​ ，之间以一个空格隔开。 输出描述 计算出小核桃按照规则可以获得的最大分数。 input1 复制

```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; const int MAXN = 100005; long long cnt[MAXN]; long long dp[MAXN]; int main() { int n; cin >> n; int num; for (int i = 0; i < n; i++) { cin >> num; // 统计每个数字出现的总和 cnt[num] += num; } // 动态规划计算最大得分 dp[0] = 0; dp[1] = cnt[1]; for (int i = 2; i < MAXN; i++) { // 状态转移方程：要么不选当前数字，最大得分等于前一个数字的最大得分；要么选当前数字，最大得分等于前两个数字的最大得分加上当前数字的总和 dp[i] = max(dp[i - 1], dp[i - 2] + cnt[i]); } // 最终结果是dp数组中的最大值 cout << dp[MAXN - 1] << endl; return 0; } ``` 代码解释 1. 统计数字总和： - 用`cnt`数组统计每个数字出现的总和。输入数字后，将对应数字的总和累加到`cnt`数组中。 2. 动态规划： - 定义`dp`数组，`dp[i]`表示处理到数字`i`时能获得的最大分数。 - 初始化`dp[0] = 0`，`dp[1] = cnt[1]`。 - 状态转移方程：`dp[i] = max(dp[i - 1], dp[i - 2] + cnt[i])`。表示要么不选当前数字`i`，最大得分等于前一个数字的最大得分；要么选当前数字`i`，最大得分等于前两个数字的最大得分加上当前数字的总和。 3. 输出结果： - 最终结果是`dp`数组中的最大值，即`dp[MAXN - 1]`。 复杂度分析 - 时间复杂度：$O(N + MAXN)$，其中$N$是输入数组的长度，$MAXN$是数字的最大值。 - 空间复杂度：$O(MAXN)$，主要用于存储`cnt`和`dp`数组。 [2026-02-07 18:38:00 | AI问答 | 555点数解答]