[JLOI2014] 天天酷跑

GitHub跳转原题关系图返回列表

枚举跳跃高度和连跳次数，在固定参数下对位置与当前连跳进度做记忆化搜索，最后减去升级费用并比较最优方案。

OJ: luogu

题目 ID: P3257

难度:提高+/省选-

标签:动态规划记忆化搜索状态设计枚举

日期: 2026-06-21 13:32

目录

  1. 题意
  2. 思路
    1. 记忆化转移方程
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

在一个 n x m 的地图里，从起点 (0,1) 跑到终点线右侧。

每个格子有收益，-1 表示这个点不能经过。

开始前要先确定两件事：

  1. 跳跃高度 H
  2. 连跳数 C

升级这两个参数都要花费分数：

  • 跳跃高度每升一级花 cost1
  • 连跳数每升一级花 cost2

问最终最大净收益是多少，并输出对应的最小连跳数、最小跳跃高度。

如果无论如何都跑不出终点，就输出 mission failed。

思路

先看一个可以直接验证想法的朴素解：

cpp
// brute.cpp：小数据暴力搜索，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30;
const int MAXM = 10;
const long long NEG_INF = -(1LL << 60);

int n, m, cost1, cost2;
int mp[MAXM][MAXN];
int H, C;

long long brute_dfs(int x, int y, int used) {
    if (x > n) {
        return 0;
    }
    if (mp[y][x] == -1) {
        return NEG_INF;
    }
    if (y == 1) {
        used = 0;
    }

    long long best = NEG_INF;

    if (y == 1) {
        best = max(best, brute_dfs(x + 1, 1, 0));
    }
    else {
        if (y - 1 == 1) {
            best = max(best, brute_dfs(x + 1, 1, 0));
        }
        else {
            best = max(best, brute_dfs(x + 1, y - 1, used));
        }
    }

    if (used < C && y + H <= m) {
        long long extra = 0;
        bool ok = true;
        for (int i = 1; i < H; i++) {
            int nx = x + i;
            int ny = y + i;
            if (nx > n) {
                break;
            }
            if (mp[ny][nx] == -1) {
                ok = false;
                break;
            }
            extra += mp[ny][nx];
        }
        if (ok) {
            best = max(best, extra + brute_dfs(x + H, y + H, used + 1));
        }
    }

    if (best == NEG_INF) {
        return NEG_INF;
    }
    return best + mp[y][x];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> cost1 >> cost2;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> mp[i][j];
        }
    }

    long long best_score = NEG_INF;
    int best_c = -1;
    int best_h = -1;

    for (int c = 1; c <= 5; c++) {
        for (int h = 1; c * h < m; h++) {
            C = c;
            H = h;

            long long ret = brute_dfs(0, 1, 0);
            if (ret == NEG_INF) {
                continue;
            }

            long long score = ret - 1LL * cost1 * (h - 1) - 1LL * cost2 * (c - 1);

            if (score > best_score ||
                (score == best_score && (c < best_c || (c == best_c && h < best_h)))) {
                best_score = score;
                best_c = c;
                best_h = h;
            }
        }
    }

    if (best_c == -1) {
        cout << "mission failed\n";
    }
    else {
        cout << best_score << ' ' << best_c << ' ' << best_h << '\n';
    }

    return 0;
}

这题最麻烦的地方在于：跳跃高度和连跳数不是过程中的决策，而是开始前一次性设定好的。

因此最自然的处理方式是：

  1. 先枚举跳跃高度 H
  2. 再枚举连跳数 C
  3. 在固定 (H, C) 的前提下，求一条最优路径

接下来只看固定参数下怎么做。

把状态记成：

  • 当前横坐标 x
  • 当前高度 y
  • 这一轮腾空过程中已经用了多少次跳跃 used

如果当前在地面：

  1. 可以继续向前跑一格
  2. 可以开始一次跳跃

如果当前在空中：

  1. 可以继续下落一格
  2. 如果还没超过连跳次数，就可以再次起跳

注意这里的“再次起跳”是从当前位置再斜着向右上跳 H 格，中间经过的上升点收益要一起算进去。

这就形成了一个只向右转移的多段图，所以可以直接做记忆化搜索。

记忆化转移方程

固定 (H,C) 后，设 dfs(x,y,used) 表示从当前位置继续跑到终点线右侧的最大额外收益。 主要转移有两类：

dfs(x,y,used)←dfs(x+1,y′,used′) dfs(x,y,used) \leftarrow dfs(x+1,y',used')

表示继续向右跑或在空中下落；若还能继续跳，则：

dfs(x,y,used)←extra+dfs(x+H,y+H,used+1) dfs(x,y,used) \leftarrow extra + dfs(x+H,y+H,used+1)

其中 extra 是起跳过程中经过的中间格收益。 每组 (H,C) 求出的路径收益还要减去升级费用。

再注意一个合法性约束：

  • 既然设定好参数后必须保证不会跳出高度上限

那么只需要枚举满足：

  • C * H < m

的参数组合即可。

对于每组 (H, C)，求出最大路径收益后，再减去升级代价：

  • cost1 * (H - 1) + cost2 * (C - 1)

最后按题意要求比较：

  1. 净收益最大
  2. 若净收益相同，连跳数最小
  3. 若还相同，跳跃高度最小

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int MAXM = 25;
const long long NEG_INF = -(1LL << 60);

int n, m, cost1, cost2;
int mp[MAXM][MAXN];
long long dp[MAXN][MAXM][6];
bool vis[MAXN][MAXM][6];
int H, C;

// 记忆化搜索：
// dfs(x, y, used) 表示当前在 (x, y)，当前这次腾空过程已经用了 used 次跳跃，
// 从这里跑到终点线右侧的最大额外收益（包含当前位置收益，不含起点 (0,1)）。
long long dfs(int x, int y, int used) {
    if (x > n) {
        return 0;
    }
    if (mp[y][x] == -1) {
        return NEG_INF;
    }
    if (y == 1) {
        used = 0;
    }
    if (vis[x][y][used]) {
        return dp[x][y][used];
    }
    vis[x][y][used] = true;

    long long best = NEG_INF;

    if (y == 1) {
        // 在地面上可以继续向前跑一格。
        best = max(best, dfs(x + 1, 1, 0));
    }
    else {
        // 在空中可以继续下落一格；落地后连跳计数清零。
        if (y - 1 == 1) {
            best = max(best, dfs(x + 1, 1, 0));
        }
        else {
            best = max(best, dfs(x + 1, y - 1, used));
        }
    }

    // 如果当前还能继续跳一次，则尝试从当前位置起跳/连跳。
    if (used < C && y + H <= m) {
        long long extra = 0;
        bool ok = true;

        // 起跳/连跳过程中，会上升经过这些中间点。
        for (int i = 1; i < H; i++) {
            int nx = x + i;
            int ny = y + i;
            if (nx > n) {
                break;
            }
            if (mp[ny][nx] == -1) {
                ok = false;
                break;
            }
            extra += mp[ny][nx];
        }

        if (ok) {
            best = max(best, extra + dfs(x + H, y + H, used + 1));
        }
    }

    if (best == NEG_INF) {
        dp[x][y][used] = NEG_INF;
    }
    else {
        dp[x][y][used] = best + mp[y][x];
    }
    return dp[x][y][used];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> cost1 >> cost2;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> mp[i][j];
        }
    }

    long long best_score = NEG_INF;
    int best_c = -1;
    int best_h = -1;

    for (int c = 1; c <= 5; c++) {
        for (int h = 1; c * h < m; h++) {
            C = c;
            H = h;
            memset(vis, 0, sizeof(vis));

            long long ret = dfs(0, 1, 0);
            if (ret == NEG_INF) {
                continue;
            }

            long long score = ret - 1LL * cost1 * (h - 1) - 1LL * cost2 * (c - 1);

            if (score > best_score ||
                (score == best_score && (c < best_c || (c == best_c && h < best_h)))) {
                best_score = score;
                best_c = c;
                best_h = h;
            }
        }
    }

    if (best_c == -1) {
        cout << "mission failed\n";
    }
    else {
        cout << best_score << ' ' << best_c << ' ' << best_h << '\n';
    }

    return 0;
}

复杂度

设可枚举的参数组数量为 S。

对每组 (H, C)，状态数大约是：

  • O(n∗m∗C)O(n * m * C)

而 m <= 20、C <= 5，状态非常小。

总复杂度可以看作 O(Snm)O(Snm)，在本题范围内可以通过。

总结

这题的关键有两层：

  1. 开始前先枚举固定的跳跃参数
  2. 固定参数后，把过程看成一个只会向右推进的记忆化搜索

本质上是“参数枚举 + 小状态 DP”的组合题。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析