1 条题解
-
0
题意简述
从格子 跳到格子 ,每步恰好跳 格,不能越过 ,且相邻两跳距离不同;得分为所有落点(含 与 )的价值之和,求最大得分。
思路
暴力(部分分)
DFS 枚举每步跳 、落到 结算,复杂度 , 左右可过(对应测试点 1–7,;测试点 8 起必 TLE)。
正解:线性 DP
为什么需要额外状态:站在格子 时,下一步允许跳的距离集合由"上一跳跳了几格"决定,所以只有 (位置, 上一跳距离) 才是完整的无后效状态。
状态:(,代码中记作
f[k][i])= 上一步跳 格、落在格子 时的最大得分;不可达置 。转移():
$$f_{k,i} = v_i + \max_{k' \ne k,\; i - k \ge 1} f_{k',\; i-k}$$- 若 :从起点直接跳来,没有"上一跳"限制,直接 ;
- 若 :不合法;
- 若所有 都不可达,则 不可达。
答案: 时输出 (不跳);否则输出 。注意只有落在 的状态才算答案,不能取中间格子的最大值。
两个值得玩味的小结构
- : 需要连续两跳 1 格,违规;唯一方案 (跳 2 格)。所以格子 2 的价值永远拿不到——样例 2 中价值 100 的格子 2 是诱饵。
- "被困"现象:若跳到某格后,所有不违规的跳法都会越过 ,就无法到达终点(样例 1 中格子 3 价值 10,但 之后只能 ,再从 4 出发只能跳 2 或 3 格,全部越界)。因此"价值高的格子能踩则踩"的贪心是错的。
复杂度
时间 ,空间 。每个状态只依赖 处的 9 个值,理论上可滚动到 空间,但 无必要。
参考代码(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 起跳时误套"上一跳"限制,把 、 判成非法。
- 把中间格子的 值混进答案——必须只取 。
- 不可达状态要用足够小的哨兵(如 )并在转移前判掉,否则 加上 后的"伪值"可能参与比较;更不能初始化成 (全负数据会错,测试点 11 专卡)。
- 得分绝对值可达 ,必须 long long。
- 约束限制的是相邻两跳,相隔的两次跳跃距离相同没有关系(如 合法)。
测试点设计
测试点 设计意图 1–2 题面样例(样例 1 演示"被困",样例 2 是 陷阱) 3 ,答案 4 全负,答案 5 全 1:答案是 而不是 6 全负:最优是 直接跳 3(不走中间格) 7 手工构造:大价值格子"被困",贪心会错 8 随机,卡 暴力 9–12 满规模随机:全值域 / 全正 / 全负(必须到达,不能"不跳")/
- 1
信息
- ID
- 4
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者