第三部分：题目分析与标准代码

1. 动态规划思路

定义 $dp[i]$ 为：考虑前 $i$ 个据点时，能获得的最大价值。 对于第 $i$ 个据点，只有两种选择：

1. 不选第 $i$ 个：那么最大价值等于前 $i-1$ 个据点的最大价值。即 $dp[i] = dp[i-1]$。
2. 选第 $i$ 个：那么第 $i-1$ 个一定不能选，只能从前 $i-2$ 个据点的最大价值转移过来，并加上 $V_i$。即 $dp[i] = dp[i-2] + V_i$。

状态转移方程：

空间优化： 计算 $dp[i]$ 只需要用到前两个状态。我们可以用三个变量 prev2、prev1、curr 来代替数组，将空间复杂度从 $O(N)$ 降为 $O(1)$。

2. 标准代码 (C++14)

/**
 * 题目：守卫长安 (Guarding Chang'an)
 * 难度：GESP 6级
 * 算法：线性动态规划 (Linear DP)
 */

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

using namespace std;

// 开启 IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

const int MAXN = 1000005;
// dp 数组，用于存储状态
// dp[i] 表示前 i 个据点的最大价值
// 使用 long long 防止累加溢出
long long dp[MAXN];
long long v[MAXN]; // 存储价值

int main() {
    fast_io();

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

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

    // 边界处理
    if (N == 1) {
        cout << v[1] << endl;
        return 0;
    }

    // 初始化 DP
    // 考虑前1个，必选第1个
    dp[1] = v[1];
    // 考虑前2个，选较大的那个（不能同时选）
    dp[2] = max(v[1], v[2]);

    // 状态转移
    for (int i = 3; i <= N; ++i) {
        // 核心方程：max(不选i, 选i)
        dp[i] = max(dp[i-1], dp[i-2] + v[i]);
    }

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

    return 0;
}

第四部分：数据生成器

这是修正后的数据生成器，修复了 $N=1$ 时数组越界的问题，并包含全面的测试点。

/**
 * GESP 6级 [守卫长安] - 数据生成器
 * 修复：解决 solve 函数中 N=1 时的越界访问问题
 */
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
long long solve(int N, const vector<long long>& v) {
    if (N == 0) return 0;
    if (N == 1) return v[0]; // 只有一个元素，直接返回
    
    // 使用滚动数组优化空间
    long long prev2 = v[0];             // dp[0]
    long long prev1 = max(v[0], v[1]);  // dp[1]
    
    for (int i = 2; i < N; ++i) {
        long long curr = max(prev1, prev2 + v[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

// 辅助函数
long long randVal(long long max_val) {
    if (max_val == 0) return 0;
    return rand() % max_val;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N;
        vector<long long> v;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 4; v = {1, 2, 3, 1};
        }
        else if (i == 2) {
            // 样例2
            N = 5; v = {2, 7, 9, 3, 1};
        }
        else if (i == 3) {
            // 极小边界 N=1 (测试越界修复)
            N = 1; v = {100};
        }
        else if (i == 4) {
            // 极小边界 N=2
            N = 2; v = {10, 20};
        }
        else if (i == 5) {
            // 全0测试
            N = 100;
            for(int k=0; k<N; k++) v.push_back(0);
        }
        else if (i == 6) {
            // 递增序列 (倾向于选后面的)
            N = 100;
            for(int k=0; k<N; k++) v.push_back(k + 1);
        }
        else if (i == 7) {
            // 只有中间一个极大值 (必选)
            N = 1000;
            for(int k=0; k<N; k++) v.push_back(10);
            v[500] = 100000;
        }
        else if (i == 8) {
            // 奇偶波动 (100, 1, 100, 1...) 贪心陷阱
            N = 2000;
            for(int k=0; k<N; k++) v.push_back(k % 2 == 0 ? 100 : 1);
        }
        else {
            // 大规模随机 (N=10^6)
            N = 1000000;
            long long max_v = (i == 9) ? 100 : 1000000000; // Case 9 小数值，Case 10 大数值
            for(int k=0; k<N; k++) {
                v.push_back(randVal(max_v));
            }
        }

        // 写入输入
        fin << N << "\n";
        for (int k = 0; k < N; ++k) {
            fin << v[k] << (k == N-1 ? "" : " ");
        }
        fin << "\n";

        // 写入输出
        fout << solve(N, v) << "\n";

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done! All files generated." << endl;
    return 0;
}