CSP - J组难题：小核桃数组规则谜题求解与代码详解

```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`数组。 ######[AI问答 | 555点数解答 | 2026-02-07 18:38:00]