版本2代码RTE

最长类斐波那契子序列 (Longest Fibonacci-Like Subsequence)

教练诊断：为什么 Version 2 崩了？

孩子，看到 Segmentation fault（段错误），你脑子里应该立刻弹出三个字：“越界了”。

我们在写 Version 2 的时候，数组定义是 int dp[2505][2505]，这对应的是最初 $N=2500$ 的数据范围。但是为了区分复杂度，我们刚才把数据生成器的 $N$ 提高到了 5000。当程序试图访问 dp[4999][5000] 时，它就像开车冲出了悬崖，直接崩溃。

此外， Version 2 的 unordered_map 在 $N=5000$ 时会因为频繁的哈希冲突和内存分配变得非常慢。

修正版 Version 2：适配 N=5000 与内存管理

在 OI 竞赛中，如果 $N=5000$，二维数组 int dp[5005][5005] 占用大约 95.5 MiB。如果题目给的内存限制是 128 MiB，这是安全的；如果只有 64 MiB，我们就得换成哈希表或者滚动数组。

这里我们按照 128 MiB 标准，为你提供修正后的代码：

核心知识点：全局大数组与下标映射

1. 静态分配：大数组必须开在全局区（函数外部），否则会直接“爆栈”。
2. 安全性检查：在进行 target 查找前，先通过哈希表确定索引，确保逻辑严密。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

// 1. 解决 RE：根据最新的数据规模 N=5000，调整数组大小
// 5005 * 5005 * 4 bytes ≈ 95.5 MB，适合 128MB 以上的题目
int dp[5005][5005];

int solve_v2_fixed(int n, vector<int>& nums) {
    // 2. 优化：预先 reserve 哈希表空间，减少扩容带来的时间消耗
    unordered_map<int, int> val_to_idx;
    val_to_idx.reserve(n);
    for (int i = 0; i < n; ++i) val_to_idx[nums[i]] = i;

    int max_len = 0;
    
    // 初始化 DP 状态
    // 注意：只初始化到当前 n 的范围，节省时间
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j) dp[j][i] = 2;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            int target = nums[i] - nums[j];
            
            // 3. 逻辑约束：类斐波那契要求 A[k] < A[j] < A[i]
            // 由于 nums 严格递增，nums[k] < nums[j] 等价于 k < j
            if (target < nums[j]) {
                auto it = val_to_idx.find(target);
                if (it != val_to_idx.end()) {
                    int k = it->second;
                    // 状态转移：从以 (k, j) 结尾的状态转移到 (j, i)
                    dp[j][i] = dp[k][j] + 1;
                    if (dp[j][i] > max_len) max_len = dp[j][i];
                }
            }
        }
    }
    
    // 类斐波那契序列长度必须 >= 3
    return max_len >= 3 ? max_len : 0;
}

int main() {
    // 提升 IO 效率
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<int> nums(n);
    for (int i = 0; i < n; ++i) cin >> nums[i];

    cout << solve_v2_fixed(n, nums) << endl;

    return 0;
}

OI 教练的避坑指南：

1. 内存估算公式： 在赛场上，一定要算一下：行 * 列 * sizeof(类型) / 1024 / 1024 = ? MiB。

   • 5000 * 5000 * 4 (int) / 1024 / 1024 ≈ 95.4 MiB
   • 5000 * 5000 * 2 (short) / 1024 / 1024 ≈ 47.7 MiB —— 如果内存紧，把 int 改成 short！ 本题长度不超过 5000，short 完全够用。

2. Segmentation Fault 的三大原因：

   • 数组开小了：最常见，如你这次遇到的。
   • 局部变量太大：在函数内部定义 int dp[5000][5000] 会导致栈溢出。永远记得把大数组开到全局！
   • 指针/下标为负数：比如 nums[i] - nums[j] 算出了一个负数，而你直接把它当索引。

3. 为什么不推荐用 std::map？ 在 $N=5000$ 的双重循环中，std::map（红黑树）会多出一个 $\log N$ 的开销，总复杂度变成 $O(N^2 \log N)$，而且常数巨大，极易 TLE。unordered_map 或双指针法才是正解。

现在，换上这个修正版的 Version 2，那 100 分就稳了！