1 条题解

  • 0
    @ 2026-11-11 23:35:43

    题意简述

    从格子 11 跳到格子 nn,每步恰好跳 1/2/31/2/3 格,不能越过 nn,且相邻两跳距离不同;得分为所有落点(含 11 与 nn)的价值之和,求最大得分。

    思路

    暴力(部分分)

    DFS 枚举每步跳 1/2/31/2/3、落到 nn 结算,复杂度 O(3n)O(3^n),n≤15n \le 15 左右可过(对应测试点 1–7,n≤5n \le 5;测试点 8 起必 TLE)。

    正解:线性 DP

    为什么需要额外状态:站在格子 ii 时,下一步允许跳的距离集合由"上一跳跳了几格"决定,所以只有 (位置, 上一跳距离) 才是完整的无后效状态。

    状态:fk,if_{k,i}(k∈{1,2,3}k \in \{1, 2, 3\},代码中记作 f[k][i])= 上一步跳 kk 格、落在格子 ii 时的最大得分;不可达置 −∞-\infty。

    转移(1≤i≤n1 \le i \le n):

    $$f_{k,i} = v_i + \max_{k' \ne k,\; i - k \ge 1} f_{k',\; i-k}$$
    • 若 i−k=1i - k = 1:从起点直接跳来,没有"上一跳"限制,直接 fk,i=v1+vif_{k,i} = v_1 + v_i;
    • 若 i−k<1i - k < 1:不合法;
    • 若所有 fk′,  i−kf_{k',\; i-k} 都不可达,则 fk,if_{k,i} 不可达。

    答案:n=1n = 1 时输出 v1v_1(不跳);否则输出 max⁡{f1,n, f2,n, f3,n}\max\{f_{1,n},\, f_{2,n},\, f_{3,n}\}。注意只有落在 nn 的状态才算答案,不能取中间格子的最大值。

    两个值得玩味的小结构

    • n=3n=3:1→2→31 \to 2 \to 3 需要连续两跳 1 格,违规;唯一方案 1→31 \to 3(跳 2 格)。所以格子 2 的价值永远拿不到——样例 2 中价值 100 的格子 2 是诱饵。
    • "被困"现象:若跳到某格后,所有不违规的跳法都会越过 nn,就无法到达终点(样例 1 中格子 3 价值 10,但 1→31 \to 3 之后只能 3→43 \to 4,再从 4 出发只能跳 2 或 3 格,全部越界)。因此"价值高的格子能踩则踩"的贪心是错的。

    复杂度

    时间 O(9n)O(9n),空间 O(n)O(n)。每个状态只依赖 i−1,i−2,i−3i-1, i-2, i-3 处的 9 个值,理论上可滚动到 O(1)O(1) 空间,但 n≤105n \le 10^5 无必要。

    参考代码(C++)

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    long long f[4][100005];
    
    int main() {
        freopen("jump.in", "r", stdin);
        freopen("jump.out", "w", stdout);
    
        int n;
        if (scanf("%d", &n) != 1) return 0;
        static long long v[100005];
        for (int i = 1; i <= n; i++) scanf("%lld", &v[i]);
        if (n == 1) {  // 起点即终点,不跳
            printf("%lld\n", v[1]);
            return 0;
        }
        const long long NEG = -(1LL << 60);
        for (int k = 1; k <= 3; k++)
            for (int i = 0; i <= n; i++) f[k][i] = NEG;
        for (int i = 2; i <= n; i++) {
            for (int k = 1; k <= 3; k++) {
                int j = i - k;
                if (j < 1) continue;
                long long best = NEG;
                if (j == 1) {
                    best = v[1];  // 从起点起跳,没有"上一次跳跃"的限制
                } else {
                    for (int k2 = 1; k2 <= 3; k2++)
                        if (k2 != k) best = max(best, f[k2][j]);
                }
                if (best > NEG / 2) f[k][i] = best + v[i];
            }
        }
        long long ans = max(max(f[1][n], f[2][n]), f[3][n]);
        printf("%lld\n", ans);
        return 0;
    }
    

    易错点

    1. 忘记 n=1n=1:不跳,答案就是 v1v_1(可能为负)。
    2. 从格子 1 起跳时误套"上一跳"限制,把 1→21 \to 2、1→31 \to 3 判成非法。
    3. 把中间格子的 ff 值混进答案——必须只取 fk,nf_{k,n}。
    4. 不可达状态要用足够小的哨兵(如 −260-2^{60})并在转移前判掉,否则 −∞-\infty 加上 viv_i 后的"伪值"可能参与比较;更不能初始化成 00(全负数据会错,测试点 11 专卡)。
    5. 得分绝对值可达 105×109=101410^5 \times 10^9 = 10^{14},必须 long long。
    6. 约束限制的是相邻两跳,相隔的两次跳跃距离相同没有关系(如 1,2,11, 2, 1 合法)。

    测试点设计

    测试点 设计意图
    1–2 题面样例(样例 1 演示"被困",样例 2 是 n=3n=3 陷阱)
    3 n=1n=1,答案 −7-7
    4 n=2n=2 全负,答案 −2×109-2 \times 10^9
    5 n=3n=3 全 1:答案是 22 而不是 33
    6 n=4n=4 全负:最优是 1→41 \to 4 直接跳 3(不走中间格)
    7 手工构造:大价值格子"被困",贪心会错
    8 n=1000n=1000 随机,卡 O(3n)O(3^n) 暴力
    9–12 满规模随机:全值域 / 全正 / 全负(必须到达,不能"不跳")/ n=99999n=99999
    • 1

    信息

    ID
    4
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    2
    已通过
    2
    上传者