五、 标准题解代码 (C++14)

/**
 * 题目：根的向地性生长 (Geotropic Growth of Roots)
 * 算法：动态规划 / 数字三角形模型 (DP / Number Triangle)
 * 难度：GESP 5级 / CSP-J T2
 */

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

using namespace std;

// 定义一个极小值，表示不可达
// 因为 V >= 0，且 N<=1000，最大可能和为 1000*100 = 10^5
// 所以 -1e9 足够小
const int INF = -1e9;

int main() {
    // 1. I/O 加速
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, S;
    if (!(cin >> N >> M >> S)) return 0;

    // 使用 vector 存储地图和 DP 表
    // 下标从 1 开始，开 M+2 大小方便处理边界
    vector<vector<int>> map(N + 1, vector<int>(M + 2, -1));
    vector<vector<int>> dp(N + 1, vector<int>(M + 2, INF));

    // 2. 读入地图
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            cin >> map[i][j];
        }
    }

    // 3. 初始化第一行 DP
    // 只有起点 S 是可达的
    // 题目保证起点不是石头，所以直接赋值
    dp[1][S] = map[1][S];

    // 4. 动态规划过程
    for (int i = 2; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            // 如果当前位置是石头，则根无法生长到这里，保持 INF
            if (map[i][j] == -1) {
                dp[i][j] = INF;
                continue;
            }

            // 寻找上一行能到达这里的最大值
            // 上一行可能的位置：j-1, j, j+1
            // 注意：由于我们列开了 M+2，所以 j-1 和 j+1 不会越界访问
            // 但那些边界位置的值初始化为 INF，不会影响 max 结果
            int prev_max = INF;
            prev_max = max(prev_max, dp[i-1][j-1]);
            prev_max = max(prev_max, dp[i-1][j]);
            prev_max = max(prev_max, dp[i-1][j+1]);

            // 如果上一行没有任何位置能到达这里（即全是不可达）
            if (prev_max == INF) {
                dp[i][j] = INF;
            } else {
                dp[i][j] = prev_max + map[i][j];
            }
        }
    }

    // 5. 寻找答案
    int ans = INF;
    for (int j = 1; j <= M; ++j) {
        ans = max(ans, dp[N][j]);
    }

    // 如果 ans 还是 INF，说明最后一行没有任何位置可达
    if (ans == INF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

时间与空间复杂度分析

• 时间复杂度：
  • 双重循环遍历整个网格。
  • $O(N \times M)$。
• 空间复杂度：
  • 使用了两个二维数组 map 和 dp。
  • $O(N \times M)$。
  • 优化建议：实际上 DP 只需要用到上一行的数据，可以用“滚动数组”将空间优化到 $O(M)$。但这对于 GESP 5级来说不是必须的，且二维数组更直观易懂。

六、 数据生成器 (Generator.cpp)

/**
 * 题目：根的向地性生长
 * 数据生成器
 */

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

using namespace std;

mt19937 rng(time(0));
const int INF_VAL = -1e9;

// 核心解法
int solve(int N, int M, int S, const vector<vector<int>>& grid) {
    vector<vector<int>> dp(N + 1, vector<int>(M + 2, INF_VAL));
    dp[1][S] = grid[1][S];
    for(int i=2; i<=N; ++i) {
        for(int j=1; j<=M; ++j) {
            if(grid[i][j] == -1) continue;
            int prev = INF_VAL;
            if(j>1) prev = max(prev, dp[i-1][j-1]);
            prev = max(prev, dp[i-1][j]);
            if(j<M) prev = max(prev, dp[i-1][j+1]);
            
            if(prev != INF_VAL) dp[i][j] = prev + grid[i][j];
        }
    }
    int ans = INF_VAL;
    for(int j=1; j<=M; ++j) ans = max(ans, dp[N][j]);
    return (ans == INF_VAL) ? -1 : ans;
}

void make_case(int id) {
    int N, M, S;
    vector<vector<int>> grid;

    switch(id) {
        case 1: // 修正后的样例
            N = 4; M = 5; S = 3;
            grid = {
                {0,0,0,0,0,0}, // padding 0
                {0, 0, 0, 10, 0, 0},
                {0, 2, 5, -1, 3, 1},
                {0, -1, 8, 4, 2, 6},
                {0, 1, 3, 5, -1, 9}
            };
            break;
        case 2: // 极小数据
            N = 2; M = 3; S = 2;
            grid = vector<vector<int>>(N+1, vector<int>(M+1));
            grid[1][2] = 5;
            grid[2][1]=1; grid[2][2]=2; grid[2][3]=3;
            break;
        case 3: // 一条直线
            N = 10; M = 1; S = 1;
            grid = vector<vector<int>>(N+1, vector<int>(M+1));
            for(int i=1; i<=N; ++i) grid[i][1] = 10;
            break;
        case 4: // 全是石头，立马堵死
            N = 5; M = 5; S = 3;
            grid = vector<vector<int>>(N+1, vector<int>(M+1));
            grid[1][3] = 10;
            for(int j=1; j<=M; ++j) grid[2][j] = -1;
            break;
        case 5: // 蛇形走位（构造只有一条路）
            N = 10; M = 10; S = 1;
            grid = vector<vector<int>>(N+1, vector<int>(M+1, -1)); // 默认全石头
            grid[1][1] = 1;
            {
                int c = 1;
                for(int r=2; r<=N; ++r) {
                    if(r%2==0 && c<M) c++; 
                    else if(r%2!=0 && c>1) c--;
                    grid[r][c] = 1; // 只有这一格有路
                }
            }
            break;
        case 6: // 随机小数据
            N = 20; M = 20; S = rng()%M + 1;
            grid = vector<vector<int>>(N+1, vector<int>(M+1));
            for(int i=1; i<=N; ++i)
                for(int j=1; j<=M; ++j)
                    grid[i][j] = (rng()%10 < 2) ? -1 : rng()%100;
            grid[1][S] = 100; // 保证起点非石头
            break;
        case 7: // 随机中数据
            N = 100; M = 100; S = 50;
            grid = vector<vector<int>>(N+1, vector<int>(M+1));
            for(int i=1; i<=N; ++i)
                for(int j=1; j<=M; ++j)
                    grid[i][j] = (rng()%10 < 3) ? -1 : rng()%100;
            grid[1][S] = 100;
            break;
        case 8: // 大数据，稀疏石头
            N = 1000; M = 1000; S = 500;
            grid = vector<vector<int>>(N+1, vector<int>(M+1));
            for(int i=1; i<=N; ++i)
                for(int j=1; j<=M; ++j)
                    grid[i][j] = (rng()%20 < 1) ? -1 : rng()%100;
            grid[1][S] = 100;
            break;
        case 9: // 大数据，密集石头 (容易无解)
            N = 1000; M = 1000; S = 500;
            grid = vector<vector<int>>(N+1, vector<int>(M+1));
            for(int i=1; i<=N; ++i)
                for(int j=1; j<=M; ++j)
                    grid[i][j] = (rng()%10 < 4) ? -1 : rng()%100;
            grid[1][S] = 100;
            break;
        case 10: // 最大值测试 (全100)
            N = 1000; M = 1000; S = 1;
            grid = vector<vector<int>>(N+1, vector<int>(M+1, 100));
            break;
    }

    string in_file = to_string(id) + ".in";
    ofstream fout_in(in_file);
    fout_in << N << " " << M << " " << S << "\n";
    for(int i=1; i<=N; ++i) {
        for(int j=1; j<=M; ++j) {
            fout_in << grid[i][j] << (j==M?"":" ");
        }
        fout_in << "\n";
    }
    fout_in.close();

    string out_file = to_string(id) + ".out";
    ofstream fout_out(out_file);
    fout_out << solve(N, M, S, grid) << "\n";
    fout_out.close();
    
    cout << "Generated Case " << id << endl;
}

int main() {
    for(int i=1; i<=10; ++i) make_case(i);
    return 0;
}

这道题利用植物根系向重力生长的生物学现象，完美包装了经典的数字三角形 DP 问题。通过加入“石头”障碍，增加了题目的趣味性和逻辑判断要求，非常适合 GESP 5级 学生的思维训练。