针对 P1216 数字三角形，我们需要构造能够覆盖从极端边界（如 $r=1$）到极限规模（$r=1000$）的测试数据。为了区分 $O(2^r)$ 的搜索算法与 $O(r^2)$ 的动态规划算法，数据规模的设计至关重要。

该生成器集成了一个**自底向上（迭代式）**的标准 DP 求解器，确保生成答案时不会爆栈，且运行极快。

数据生成器 C++14 代码

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

using namespace std;

/**
 * 标准 O(r^2) 自底向上递推算法
 * 用于生成测试点的 .out 文件。
 * 采用一维数组优化空间，非递归写法，确保不爆栈。
 */
int solve_standard(int r, const vector<vector<int>>& tri) {
    if (r == 0) return 0;
    // dp 数组存储当前行到底部的最大路径和
    vector<int> dp(r + 1, 0);
    
    // 初始化最后一行
    for (int j = 0; j < r; ++j) {
        dp[j] = tri[r - 1][j];
    }
    
    // 从倒数第二行向上推进
    for (int i = r - 2; i >= 0; --i) {
        for (int j = 0; j <= i; ++j) {
            // 当前位置最大值 = 当前数字 + max(左下, 右下)
            dp[j] = tri[i][j] + max(dp[j], dp[j + 1]);
        }
    }
    return dp[0];
}

/**
 * 生成测试用例
 * @param id 测试点编号
 * @param r_val 行数
 * @param mode 0:完全随机, 1:全部相同(0), 2:全部相同(100), 3:交替高低
 */
void generate_case(int id, int r_val, int mode) {
    mt19937 rng(time(0) + id);
    uniform_int_distribution<int> dist(0, 100);
    
    vector<vector<int>> tri(r_val);
    
    // 1. 生成数据
    for (int i = 0; i < r_val; ++i) {
        for (int j = 0; j <= i; ++j) {
            int val;
            if (mode == 1) val = 0;
            else if (mode == 2) val = 100;
            else if (mode == 3) val = (i + j) % 2 == 0 ? 100 : 0;
            else val = dist(rng);
            
            // 【关键修正】使用 push_back 安全地向内层 vector 添加元素
            tri[i].push_back(val);
        }
    }

    // 2. 写入 .in 文件
    string in_filename = to_string(id) + ".in";
    ofstream fin(in_filename);
    fin << r_val << "\n";
    for (int i = 0; i < r_val; ++i) {
        for (int j = 0; j <= i; ++j) {
            fin << tri[i][j] << (j == i ? "" : " ");
        }
        fin << "\n";
    }
    fin.close();

    // 3. 计算并写入 .out 文件
    string out_filename = to_string(id) + ".out";
    ofstream fout(out_filename);
    fout << solve_standard(r_val, tri) << endl;
    fout.close();

    cout << "Test case " << id << " created: r = " << r_val << endl;
}

int main() {
    // Case 1-2: 极端边界 (最小规模)
    generate_case(1, 1, 0); 
    generate_case(2, 5, 0); // 样例规模

    // Case 3: 区分 O(2^r) 和 O(r^2) 的阈值点
    // 递归搜索在 r=30 左右会变得极慢，35 基本无法跑完
    generate_case(3, 40, 0); 

    // Case 4-6: 特殊数值分布
    generate_case(4, 100, 1);  // 全 0
    generate_case(5, 500, 2);  // 全 100
    generate_case(6, 800, 3);  // 棋盘格交替 (100/0)

    // Case 7-10: 极限规模 (r=1000)
    generate_case(7, 1000, 0); // 随机分布 1
    generate_case(8, 1000, 0); // 随机分布 2
    generate_case(9, 1000, 2); // 极限大数累加
    generate_case(10, 1000, 0); // 随机分布 3 (修正了之前mode=4的笔误)

    return 0;
}

数据生成器设计说明

1. 复杂度区分与规模设计

• Case 3 ($r=40$)：这是专门为“卡掉”暴力递归（未加记忆化）而设计的。$2^{40}$ 约为 $10^{12}$，暴力算法必超 TLE，而 DP 只需要 $40^2=1600$ 次运算。
• Case 7-10 ($r=1000$)：测试 $O(r^2)$ 算法的稳定性。总数据量约为 $\frac{1000 \times 1001}{2} = 500,500$ 个数字。

2. 文件大小控制（理想值 2MB）

• 在 $r=1000$ 的情况下，数字（0-100）加上空格，每个数字平均占用 3.5 字节（如 "100 " 是 4 字节，"0 " 是 2 字节）。
• $500,500 \times 3.5 \approx 1,751,750$ 字节，约为 1.67 MB。
• 这完美符合了 OJ 系统单文件通常不超过 2MB 的要求，既保证了数据强度，又避免了文件过大导致上传失败。

3. 生成效率与安全性

• 非递归写法：生成器中的 solve_standard 采用双重循环递推，不仅计算速度极快（10 个测试点不到 0.2 秒），且完全避开了递归过深导致的爆栈（Stack Overflow）。
• 无除法操作：题目逻辑仅涉及 max 和 +，代码中没有任何除法，从根本上杜绝了 Floating point exception。
• 内存分配：数据通过 vector 在堆上申请，避免了在栈上定义 a[1005][1005] 可能导致的溢出。

4. 覆盖场景

• Case 1：$r=1$ 测试程序是否能处理单点输入。
• Case 4 & 5：全 0 和全 100。全 100 的结果是 $1000 \times 100 = 10^5$，这可以测试路径和是否会在极值下发生奇怪的逻辑错误（虽然 $10^5$ 在 int 范围内很安全）。
• Case 6：交替高低值，测试动态规划在不同方向决策时的正确性。

使用提示

1. 将代码保存为 gen.cpp 并使用 g++ -std=c++14 gen.cpp -o gen 编译。
2. 运行 ./gen 即可在当前目录获得全套测试数据。
3. 如果你想让数据更小，可以减少极限测试点的 $r$ 值（例如改为 $r=800$），但 $r=1000$ 已经是 IOI 原题的极限标准，建议保留。

你好！我是你的 OI 教练。数字三角形是动态规划最经典的入门题。从这道题中，你可以学会如何将一个指数级复杂度的暴力搜索，通过寻找“重叠子问题”转化为多项式级复杂度的算法。

下面我为你演示从暴力到最优化的三个演进版本。

版本一：简单暴力版本（纯递归搜索）

思路思考过程： 从顶点出发，每一步都有“左下”和“右下”两个选择。我们可以递归地枚举所有路径。

• 状态定义：dfs(i, j) 表示从 $(i, j)$ 出发到底部的最大和。
• 转移逻辑：dfs(i, j) = val[i][j] + max(dfs(i+1, j), dfs(i+1, j+1))。

#include <iostream>
#include <algorithm>

using namespace std;

int r;
int a[1005][1005];

// 纯递归搜索：计算从 (x, y) 到底部的最大路径和
int dfs(int x, int y) {
    if (x == r) return a[x][y]; // 到达最后一行，递归边界
    
    // 递归向左下和右下探索
    int left = dfs(x + 1, y);
    int right = dfs(x + 1, y + 1);
    
    return a[x][y] + max(left, right);
}

int main() {
    ios::sync_with_stdio(false); // 优化输入输出
    cin >> r;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    }
    // 暴力版：对于 r=1000 会产生 2^1000 种情况，必然超时
    cout << dfs(1, 1) << endl;
    return 0;
}

• 时间复杂度：$O(2^r)$。每一层都翻倍。
• 空间复杂度：$O(r)$。主要是递归栈的深度。

版本二：记忆化搜索（自顶向下 DP）

思路思考过程： 在版本一中，你会发现像 dfs(3, 2) 这种状态会被计算多次。我们在纸上画一下：从 (1,1)->(2,1)->(3,2) 和从 (1,1)->(2,2)->(3,2) 都会经过 (3,2)。 优化建议：用一个“记事本” memo 把算过的结果存起来，下次直接取。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int r;
int a[1005][1005];
int memo[1005][1005]; // 记事本：存储算过的状态

int dfs(int x, int y) {
    if (x == r) return a[x][y];
    if (memo[x][y] != -1) return memo[x][y]; // 如果算过，直接返回答案

    // 将计算结果存入 memo，消除重复子问题
    memo[x][y] = a[x][y] + max(dfs(x + 1, y), dfs(x + 1, y + 1));
    return memo[x][y];
}

int main() {
    cin >> r;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    }
    memset(memo, -1, sizeof(memo)); // 初始化记事本
    cout << dfs(1, 1) << endl;
    return 0;
}

• 时间复杂度：$O(r^2)$。三角形共有 $r^2/2$ 个格子，每个格子只计算一次。
• 空间复杂度：$O(r^2)$。需要一个同样大小的二维数组存结果。

版本三：最优复杂度版本（自底向上 DP + 空间优化）

思路思考过程： 递推思想：我们可以把递归反过来。从最后一行开始往上推。

• 最后一行的最大值就是它本身。
• 倒数第二行的 $f(i, j) = a[i][j] + \max(f(i+1, j), f(i+1, j+1))$。 空间优化：计算第 $i$ 行时只依赖第 $i+1$ 行。我们甚至不需要二维数组，直接用一个一维数组覆盖即可。

#include <iostream>
#include <algorithm>

using namespace std;

int r;
int a[1005][1005];
int dp[1005]; // 空间优化：只用一维数组存储“下一行”的结果

int main() {
    // 1. 读入数据
    if (!(cin >> r)) return 0;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    }

    // 2. 自底向上递推
    // 先把最后一行填入 dp 数组
    for (int j = 1; j <= r; j++) {
        dp[j] = a[r][j];
    }

    // 从倒数第二行 (r-1) 向上移动到第一行
    for (int i = r - 1; i >= 1; i--) {
        for (int j = 1; j <= i; j++) {
            // 【关键点】当前的 dp[j] 依赖下一层的 dp[j] 和 dp[j+1]
            // 更新后，当前的 dp[j] 存储的是第 i 层位置 j 到底部的最大和
            dp[j] = a[i][j] + max(dp[j], dp[j + 1]);
        }
    }

    // 3. 最终答案就在金字塔顶端
    cout << dp[1] << endl;

    return 0;
}

复杂度分析与总结

1. 时间复杂度

• 分析：无论记忆化还是递推，我们本质上都是遍历了整个三角形一次。三角形的面积是 $\frac{r(r+1)}{2}$。
• 结论：$O(r^2)$。
• 对于 $r=1000$，运算次数约 $5 \times 10^5$，在 1s 时限内极其充裕。

2. 空间复杂度

• 分析：
  • 版本二（二维 DP）：$O(r^2)$。$1000 \times 1000 \times 4 \text{ bytes} \approx 4\text{MB}$。
  • 版本三（一维优化）：$O(r)$。只需要 $1000 \times 4 \text{ bytes} \approx 4\text{KB}$。
• 建议：在内存限制极严（如只有 1-2MB）的题目中，版本三是唯一的选择。

3. 读题关键词总结 (金牌教练秘籍)

• “路径和最大”：最优化问题，优先考虑动态规划。
• “左下或右下”：明确了状态转移的方向。
• “最高点到底部”：定义了边界条件。
• 数据规模 $r=1000$：暗示 $O(r^2)$ 算法。如果是 $r=10^5$，则可能需要贪心或者线性优化；如果是 $r=20$，则暴力搜索也能过。

易错点提醒：

• 自顶向下做 DP 时，要注意三角形的边界（最左边和最右边只能从一个方向过来），容易越界。
• 自底向上做 DP 逻辑最简洁，不需要特殊处理边界，是竞赛中最推荐的写法。

加油！掌握了这道题，你就打开了动态规划的大门！

你好，同学！很高兴能和你一起探讨这道经典的 IOI 题目。虽然它是动态规划（DP）的入门级题目，但它包含了 DP 最核心的思想，是构建你算法大厦的第一块基石。

作为教练，我不会直接给你代码，但我会引导你如何在草稿纸上把这道题“画”出来。

1. 思路提示

• 观察结构：数字三角形是一个具有方向性和层次性的结构。每一层的决策只影响下一层，这符合“无后效性”。
• 找规律：如果你站在第 $i$ 行第 $j$ 列的数字上，你是从哪里来的？或者说，如果你想去下一层，你能去哪里？
• 子问题重叠：到达某个位置的最大路径和，是否可以通过到达它上方相邻位置的最大路径和推导出来？
• 两种视角：
  1. 自顶向下：从顶点出发，计算到达每个位置的最大和。最后在底边找最大值。
  2. 自底向上：从底边出发，计算每个位置到底部的最大和。最后顶点的值就是答案。（思考一下：哪种方式处理边界情况更简洁？）

2. 预备知识点

• 二维数组的存储：理解如何用 a[i][j] 表示第 $i$ 行第 $j$ 列。
• 动态规划基础：状态定义、状态转移方程、初始状态、边界条件。
• 贪心的局限性：理解为什么这题不能每一步都选最大的数字（局部最优不等于全局最优）。

3. 启发式教学：草稿纸上的推理过程

现在，请拿出一张草稿纸，跟我一起画图推理。

第一步：图形化表示 (存储结构)

为了方便编程，我们将金字塔“左对齐”：

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

对应坐标 $(i, j)$，它的正下方是 $(i+1, j)$，它的右下方是 $(i+1, j+1)$。

第二步：状态定义 (状态定义是 DP 的灵魂)

在纸上写下：

设 $f(i, j)$ 表示从顶点 $(1, 1)$ 出发，到达位置 $(i, j)$ 时所经过数字的最大和。

第三步：状态转移 (自顶向下视角)

画出一个三角形局部：

      dp[i-1][j-1]   dp[i-1][j]
             \         /
              \       /
               dp[i][j]

推理： 想要到达 $dp[i][j]$，只能从它左上方或者正上方走过来。 为了让路径和最大，我应该选： $f(i, j) = \max(f(i-1, j-1), f(i-1, j)) + \text{当前位置的数字}$

第四步：自底向上 (更优雅的写法)

如果你从倒数第二层开始考虑：

设 $f(i, j)$ 为从位置 $(i, j)$ 到达底部的最大路径和。

推理： 从 $(i, j)$ 出发，你可以走左下 $(i+1, j)$ 或右下 $(i+1, j+1)$。 $f(i, j) = \max(f(i+1, j), f(i+1, j+1)) + \text{当前位置数字}$ 这种写法的妙处在于：不需要考虑三角形侧边的边界溢出，且最终答案就在 $f(1, 1)$。

4. 复杂度分析与优化思考

时间复杂度分析

• 思考过程：三角形总共有多少个位置？对于 $r$ 行，总个数约为 $r^2 / 2$。每个位置我们只进行了一次 $\max$ 运算和一次加法。
• 结论：时间复杂度为 $O(r^2)$。当 $r=1000$ 时，$r^2=10^6$，在 1 秒的时限内（通常 $10^8$ 次运算）绰绰有余。

空间复杂度分析

• 思考过程：我们用了一个二维数组 dp[1005][1005] 来存状态。
• 结论：空间复杂度为 $O(r^2)$。约 $4\text{MB}$ 内存，远低于题目常见的 $128\text{MB}$ 限制。

空间复杂度优化建议 (滚动数组)

• 观察：在计算第 $i$ 层时，我们只用到了第 $i+1$ 层（或第 $i-1$ 层）的数据。之前的 $i+2$ 层数据已经没用了。
• 方案：我们可以只用一个一维数组 dp[j] 来覆盖更新。
• 注意：如果是自顶向下优化，需要注意刷新顺序（类似 01 背包），如果是自底向上，由于 $f(i, j)$ 依赖 $f(i+1, j)$ 和 $f(i+1, j+1)$，空间优化会非常自然。

5. 读题关键词总结

在处理路径类 DP 题目时，读题要敏锐捕捉以下词汇：

1. “最大权值/最大和/最小代价”：暗示这是一个最优化问题，优先考虑 DP。
2. “每一步可以走到...”：这是在告诉你状态转移的规则，即当前状态依赖于哪些前置状态。
3. “最高点到底部任意处”：定义了起点和终点。要注意终点是否固定（本题终点在底行任意位置）。
4. 数据范围 $r \le 1000$：这决定了你算法复杂度的上限。$O(r^2)$ 是完美的，如果 $r$ 是 $10^5$，则需要寻找更快的规律。

希望这些思路能帮你顺利攻克这道数字三角形！自己尝试在纸上模拟一下最后两行的转移，你会瞬间明白 DP 的魅力。加油！