题目分析

在一个 $n \times m$ 的网格中，玩家从 $(0,1)$ 出发，要到达终点。每个格子有收益值，$-1$ 表示不可通过。玩家可以设定跳跃高度 $h$ 和连跳次数 $t$，升级需要花费。目标是找到使总收益最大的参数组合。

解题思路

核心思想

使用动态规划 + 参数枚举的方法：

1. 枚举所有可能的跳跃高度和连跳次数组合
2. 对每种组合使用DP计算最大收益
3. 考虑升级成本后选择最优参数

关键技术

• 斜线前缀和：快速计算跳跃路径上的总收益
• 状态设计：记录位置、高度和连跳状态
• 边界处理：处理跳跃超出边界的情况

算法步骤

1. 预处理斜线前缀和
2. 枚举所有参数组合 (h, t)
3. 动态规划计算每种组合的最大收益
4. 减去升级成本，更新最优解
5. 按优先级输出结果

完整代码

#include <bits/stdc++.h>
#define rint register int
#define endl '\n'

using namespace std;

const int N = 1e5 + 5;
const int M = 2e1 + 5;
const int inf = 1e7;

int n, m;
int f[N][M][7];  // f[i][j][k]: 在第i列、高度j、已连跳k次时的最大收益
int c1, c2;      // 跳跃高度和连跳次数的升级成本
int c[N][M];     // 地图收益
int s[N][M];     // 斜线前缀和
int cmax, tmin, hmin;  // 最优解的收益、连跳数、跳跃高度

// 计算从(a,b)开始斜向上跳c步的总收益
int calc(int a, int b, int step) {
    return s[a + step][b + step] - s[a][b];
}

int main() {
    // 读入数据
    cin >> n >> m >> c1 >> c2;
    
    // 读入地图并预处理前缀和
    for (rint j = 1; j <= m; j++) {
        for (rint i = 1; i <= n; i++) {
            cin >> c[i][j];
            
            // 处理不可通过的点
            if (c[i][j] == -1)
                c[i][j] = -inf;
            
            // 计算斜线前缀和
            s[i][j] = c[i][j] + s[i - 1][j - 1];
        }
    }
    
    // 初始化最优解
    cmax = -inf;
    tmin = hmin = inf;
    
    // 枚举所有可能的跳跃高度
    for (rint h = 1; h < m; h++) {
        // 枚举所有可能的连跳次数
        for (rint t = 1; h * t < m && t <= 5; t++) {
            // 初始化DP数组
            for (rint i = 0; i <= n; i++) {
                for (rint j = 1; j <= m; j++) {
                    for (rint k = 0; k <= t; k++) {
                        f[i][j][k] = -inf;
                    }
                }
            }
            
            // 初始状态：起点(0,1)，连跳0次
            f[0][1][0] = 0;
            int res = -inf;  // 当前参数组合的最大收益
            
            // 动态规划主循环
            for (rint i = 0; i < n; i++) {
                for (rint j = 1; j <= m; j++) {
                    // 地面状态特殊处理
                    if (j == 1) {
                        // 在地面时，可以重置连跳次数
                        for (rint k = 1; k <= t; k++) {
                            f[i][j][0] = max(f[i][j][0], f[i][j][k]);
                        }
                        
                        // 选项1：向前走一步（保持在地面）
                        f[i + 1][j][0] = max(f[i + 1][j][0], 
                                            f[i][j][0] + c[i + 1][j]);
                        
                        // 选项2：进行一次跳跃
                        if (i + h <= n) {
                            // 正常跳跃，没有超出边界
                            f[i + h][j + h][1] = max(f[i + h][j + h][1],
                                                    f[i][j][0] + calc(i, j, h));
                        } else {
                            // 跳跃超出边界，直接到达终点
                            f[n][n - i + 1][1] = max(f[n][n - i + 1][1],
                                                    f[i][j][0] + calc(i, j, n - i));
                        }
                    } 
                    // 空中状态处理
                    else {
                        for (rint k = 1; k <= t; k++) {
                            // 选项1：下落一步
                            f[i + 1][j - 1][k] = max(f[i + 1][j - 1][k],
                                                    f[i][j][k] + c[i + 1][j - 1]);
                            
                            // 如果已达到最大连跳次数，不能继续连跳
                            if (k >= t) continue;
                            
                            // 选项2：进行连跳
                            if (i + h <= n) {
                                // 正常连跳
                                f[i + h][j + h][k + 1] = max(f[i + h][j + h][k + 1],
                                                            f[i][j][k] + calc(i, j, h));
                            } else {
                                // 连跳超出边界
                                f[n][j + n - i + 1][k + 1] = max(f[n][j + n - i + 1][k + 1],
                                                                f[i][j][k] + calc(i, j, n - i));
                            }
                        }
                    }
                }
            }
            
            // 在终点处寻找最大收益
            for (rint i = 1; i <= m; i++) {
                for (rint k = 0; k <= t; k++) {
                    res = max(f[n][i][k], res);
                }
            }
            
            // 减去升级成本
            res -= (h - 1) * c1 + (t - 1) * c2;
            
            // 更新最优解（按题目要求的优先级）
            if (res > cmax || 
                (res == cmax && t < tmin) || 
                (res == cmax && t == tmin && h < hmin)) {
                cmax = res;
                tmin = t;
                hmin = h;
            }
        }
    }
    
    // 输出结果
    if (cmax < 0) {
        cout << "mission failed" << endl;
    } else {
        cout << cmax << " " << tmin << " " << hmin << endl;
    }
    
    return 0;
}

代码说明

关键数据结构

• f[i][j][k]：DP状态数组

  • i：当前列位置（0~n）
  • j：当前高度（1~m）
  • k：已连跳次数（0~t）

• s[i][j]：斜线前缀和数组

  • 用于快速计算跳跃路径上的总收益

• c[i][j]：地图收益数组

  • 存储每个格子的收益值

算法核心

1. 状态转移规则

地面状态 (j = 1)：

• 可以重置连跳次数
• 可以选择向前走或开始跳跃

空中状态 (j > 1)：

• 只能继续下落或进行连跳
• 连跳次数不能超过最大值

2. 斜线前缀和优化

int calc(int a, int b, int step) {
    return s[a + step][b + step] - s[a][b];
}

这个函数在 $O(1)$ 时间内计算从 $(a,b)$ 开始斜向上跳 step 步的总收益。

3. 边界处理

if (i + h <= n) {
    // 正常跳跃
} else {
    // 跳跃超出边界，直接到终点
}

处理跳跃可能超出地图边界的情况。

参数枚举策略

• 跳跃高度 h：从 1 到 m-1
• 连跳次数 t：从 1 到 5，且满足 h×t < m

复杂度分析

• 时间复杂度：$O(n \cdot m \cdot t_{max} \cdot h_{max})$
  • 最坏情况：$10000 \times 20 \times 5 \times 20 = 2 \times 10^7$
• 空间复杂度：$O(n \cdot m \cdot t_{max})$