数据生成器 (Generator)

生成器包含小数据验证、交替数据（逼迫算法跳着选）、随机大数据等情况。

请保存为 gen_dp_leopard.cpp 并运行。

/**
 * Project: The Leopard's Optimal Hunt (DP Data Generator)
 * Author: Isaac Asimov (AI)
 */

#include <iostream>
#include <fstream>
#include <random>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// ==========================================
// Part 1: 标准解答逻辑
// ==========================================
class Solution {
public:
    void solve(string in_file, string out_file) {
        ifstream cin(in_file);
        ofstream cout(out_file);
        if (!cin.is_open()) return;

        int n;
        cin >> n;
        vector<int> e(n + 1);
        for(int i=1; i<=n; i++) cin >> e[i];

        if (n == 0) { cout << 0 << endl; return; }
        if (n == 1) { cout << e[1] << endl; return; }

        vector<long long> dp(n + 1);
        dp[1] = e[1];
        dp[2] = max(e[1], e[2]);

        for(int i=3; i<=n; i++) {
            dp[i] = max(dp[i-1], dp[i-2] + e[i]);
        }
        cout << dp[n] << endl;
        
        cin.close();
        cout.close();
        cout << "Generated: " << out_file << endl;
    }
};

// ==========================================
// Part 2: 数据生成逻辑
// ==========================================
mt19937 rng(2025);

int rand_int(int min, int max) {
    uniform_int_distribution<int> dist(min, max);
    return dist(rng);
}

void generate_input(int case_id) {
    string filename = to_string(case_id) + ".in";
    ofstream fout(filename);

    int n;
    vector<int> vals;

    if (case_id == 1) {
        // 样例 1
        n = 4;
        vals = {1, 2, 3, 1};
    }
    else if (case_id == 2) {
        // 样例 2
        n = 5;
        vals = {2, 7, 9, 3, 1};
    }
    else if (case_id == 3) {
        // 递增序列
        n = 10;
        for(int i=1; i<=n; i++) vals.push_back(i * 10);
    }
    else if (case_id == 4) {
        // 波峰波谷: 100 1 100 1 100
        // 诱导选 100
        n = 20;
        for(int i=0; i<n; i++) {
            if (i % 2 == 0) vals.push_back(100);
            else vals.push_back(1);
        }
    }
    else if (case_id <= 7) {
        // 随机中等
        n = rand_int(100, 1000);
        for(int i=0; i<n; i++) vals.push_back(rand_int(1, 1000));
    }
    else {
        // 大规模压力测试
        n = 100000;
        for(int i=0; i<n; i++) vals.push_back(rand_int(1, 10000));
    }

    fout << n << endl;
    for (int i = 0; i < n; i++) {
        fout << vals[i] << (i == n-1 ? "" : " ");
    }
    fout << endl;

    fout.close();
}

int main() {
    ios_base::sync_with_stdio(false);
    cout << "--- Generating DP Data ---" << endl;
    
    Solution solver;
    for (int i = 1; i <= 10; i++) {
        generate_input(i);
        string in = to_string(i) + ".in";
        string out = to_string(i) + ".out";
        solver.solve(in, out);
    }
    cout << "--- Done! ---" << endl;
    return 0;
}

阿西莫夫的解题指南

这是一道最基础的一维动态规划题目。

1. 状态定义

我们需要定义一个数组 dp。 dp[i] 表示：仅考虑前 $i$ 个猎物时，能获得的最大能量。

2. 状态转移方程

对于第 $i$ 个猎物，猎豹只有两种选择：

1. 不捕猎： 如果放弃第 $i$ 个猎物，那么最大能量就等于“考虑前 $i-1$ 个猎物时的最大能量”。

   $$\text{Option A} = dp[i-1]$$

2. 捕猎： 如果捕猎第 $i$ 个猎物，那么根据规则，第 $i-1$ 个就不能捕猎。也就是说，上一次捕猎最晚只能发生在 $i-2$。 那么最大能量就等于“考虑前 $i-2$ 个猎物时的最大能量”加上“当前猎物的能量”。

   $$\text{Option B} = dp[i-2] + E[i]$$

最终状态转移方程：

3. 边界条件

• dp[1] = E[1] （只有一个猎物，肯定抓）
• dp[2] = max(E[1], E[2]) （有两个猎物，因为相邻不能共存，只能选个大的）

C++ 标准解答 (NOIP C++14)

/**
 * 题目: 猎豹的“最佳觅食”策略 (Optimal Foraging)
 * 作者: Isaac Asimov (AI)
 * 算法: 一维动态规划 (1D DP)
 * 时间复杂度: O(N)
 */

#include <iostream>
#include <vector>
#include <algorithm> // max

using namespace std;

// 使用 long long 防止能量总和溢出
long long dp[100005];
int energy[100005];

int main() {
    // IO 优化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n

    for (int i = 1; i <= n; i++) {
        cin >> energy[i];
    }

    // 边界情况处理
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
    if (n == 1) {
        cout << energy[1] << endl;
        return 0;
    }

    // DP 初始化
    // dp[i] 代表前 i 个位置能拿到的最大值
    dp[1] = energy[1];
    dp[2] = max(energy[1], energy[2]);

    // DP 转移
    for (int i = 3; i <= n; i++) {
        // 核心方程: 选i (则加dp[i-2]) vs 不选i (即dp[i-1])
        dp[i] = max(dp[i-1], dp[i-2] + (long long)energy[i]);
    }

    // 最终答案是 dp[n]
    cout << dp[n] << endl;

    return 0;
}

阿西莫夫的点评

1. 生物学隐喻： “不能连续捕猎”这个约束，在生物学上对应着不应期（Refractory Period），在神经生物学中也是一样的道理（神经元兴奋后需要休息）。这种“必须跳过”的限制，是引入动态规划思想最自然的切入点。
2. 贪心的陷阱： 很多初学者会想：“我每次都选当前最大的不就行了吗？” 反例：5 5 10 5 5。 选 10 -> 剩下 5, 5 (不相邻)。总和 10。 DP -> 选 5, 5 (中间10不选), 5。总和 15。 这就是 DP 优于贪心的地方——它敢于为了长远的利益放弃眼前的诱惑。