一、把”下落”抽象成一张有向图
《是男人就下100层》的规则只有三条：平台只向下生成、左右各有碰撞边界、每层只能落在一块平台上。看似是反应类游戏，真正难的部分在服务端——如何在有限内存里生成无穷多平台，并在玩家每次落地时算出最优的后续路线（用于关卡难度评估、AI 托管、自动难度调参）。
把一个平台记为节点 i，属性为 (x, halfWidth, y, coins)。若玩家站在平台 j 上能够落到达平台 i，就连一条有向边 j → i。约束来自两个物理量：
| 约束 | 判定条件 | 含义 |
|---|---|---|
| 落差约束 | y_j - y_i ≤ maxFall |
重力加速度下，超出最大下落的平台够不着 |
| 水平可达 | L_j ≤ x_i ≤ R_j |
玩家可在 j 上助跑，最远跳距由水平速度与滞空时间决定 |
其中 L_j = x_j - halfWidth_j - jumpReach，R_j = x_j + halfWidth_j + jumpReach。注意 jumpReach 不是常量：滞空时间 t = sqrt(2h/g) 随落差 h 变化，所以严格意义上的可达区间随落差收窄。本文取”按最大落差计算 jumpReach“的保守上界，保证不漏解。
二、种子化 PRNG：让平台序列可复现
程序化生成的第一原则是可复现。只要种子相同，任意客户端、任意时刻生成的平台序列必须完全一致，否则回放、排行榜、断线重连全部失效。java.util.Random 的线性同余实现分布质量一般且历史版本算法不保证一致，这里用 SplitMix64——纯位运算、跨平台确定、分布质量好。
public final class SplitMix64 {
private long state;
public SplitMix64(long seed) {
this.state = seed;
}
public long nextLong() {
long z = (state += 0x9E3779B97F4A7C15L);
z = (z ^ (z >>> 30)) * 0xBF58476D1CE4E5B9L;
z = (z ^ (z >>> 27)) * 0x94D049BB133111EBL;
return z ^ (z >>> 31);
}
/** 返回 [0, bound) 内的均匀整数 */
public int nextInt(int bound) {
return (int) (Math.floorMod(nextLong() >>> 1, bound));
}
}
平台生成的关键是”可达性自举”：下一个平台的横向位置必须落在当前平台的可达范围内，否则关卡不连通。于是生成过程天然形成一条受约束的随机游走：
public final class PlatformGenerator {
public static java.util.List<Platform> generate(long seed, int count, double width) {
SplitMix64 rng = new SplitMix64(seed);
java.util.List<Platform> list = new java.util.ArrayList<>(count);
double x = width / 2.0;
double y = 0.0;
for (int i = 0; i < count; i++) {
double halfW = 28 + rng.nextInt(24); // 半宽 28~51
double gap = 40 + rng.nextInt(36); // 垂直落差 40~75
int dx = rng.nextInt(181) - 90; // 横向漂移 ±90，落在可跳范围内
x = Math.min(Math.max(x + dx, halfW), width - halfW);
list.add(new Platform(i, x, halfW, y, rng.nextInt(3) + 1));
y += gap;
}
return list;
}
}
把 x 收进 [halfW, width - halfW] 避免平台贴边穿墙；一旦收边，横向漂移空间变小，落差就要相应调小，这是关卡平滑度调参的经典取舍。
三、DP 状态与转移方程
设 dp[i] 为落到平台 i 时能累计的最大金币数：
dp[i] = coins[i] + max{ dp[j] | y_j - y_i ≤ maxFall 且 L_j ≤ x_i ≤ R_j }
按 y 升序（从顶部往下）处理节点，就保证了”所有可能的来源”都已经算完。转移条件拆成两个独立维度：
y_j - y_i ≤ maxFall是时间窗口——只保留最近maxFall高度内的平台，随i下移单调收缩；L_j ≤ x_i ≤ R_j是区间包含查询——在横坐标上找”覆盖点x_i的所有区间”里的最大dp。
于是问题变成”滑动窗口内的区间包含 + 最大值查询“。这里有个陷阱：窗口会收缩，元素会删除。而区间最大值不可逆，用前缀和技术做减法在这一类问题上完全不成立——删掉当前最大值后，必须能找出”次大”，否则结果偏乐观、路径不合法。
线段树套堆：支持惰性删除的”区间盖章”
解法是把”区间插入”转换成”在 O(log n) 个覆盖节点上盖章”，每个节点挂一个最大堆。查询点时，沿根到叶的 O(log n) 个节点各取堆顶，取最大值即为答案。删除时不做物理删除，只把过期平台的编号记下来，查询时发现堆顶是”已过期”就弹出——这就是惰性删除（lazy deletion）。
/** 线段树：区间盖章（chmax）+ 点查询最大值，支持惰性过期删除 */
public final class StabTree {
private final int size; // 离散化坐标数量
private final java.util.PriorityQueue<long[]>[] heap;
@SuppressWarnings("unchecked")
public StabTree(int size) {
this.size = size;
this.heap = new java.util.PriorityQueue[4 * size];
for (int i = 0; i < 4 * size; i++) {
// 堆顶取最大：value 降序；value 相同则按平台编号降序（越新越优）
heap[i] = new java.util.PriorityQueue<>((p, q) -> {
int c = Long.compare(q[0], p[0]);
return c != 0 ? c : Long.compare(q[1], p[1]);
});
}
}
/** 在区间 [l, r] 上"盖章"：把 (value, idx) 插入覆盖该区间的所有节点 */
public void stamp(int l, int r, long value, int idx) {
stamp(1, 0, size - 1, l, r, value, idx);
}
private void stamp(int node, int nl, int nr, int l, int r, long value, int idx) {
if (r < nl || nr < l) return;
if (l <= nl && nr <= r) {
heap[node].offer(new long[]{value, idx});
return;
}
int mid = (nl + nr) >>> 1;
stamp(node * 2, nl, mid, l, r, value, idx);
stamp(node * 2 + 1, mid + 1, nr, l, r, value, idx);
}
/**
* 查询坐标 pos 上所有覆盖区间的最大值；aliveFrom 为窗口下界，
* 编号小于 aliveFrom 的盖章已过期，堆顶遇到就弹出。
*/
public long[] query(int pos, int aliveFrom) {
long[] best = {Long.MIN_VALUE / 4, -1};
int node = 1, nl = 0, nr = size - 1;
while (true) {
java.util.PriorityQueue<long[]> h = heap[node];
while (!h.isEmpty() && h.peek()[1] < aliveFrom) {
h.poll(); // 惰性清除过期盖章
}
if (!h.isEmpty() && h.peek()[0] > best[0]) {
best = h.peek();
}
if (nl == nr) break;
int mid = (nl + nr) >>> 1;
if (pos <= mid) { node = node * 2; nr = mid; }
else { node = node * 2 + 1; nl = mid + 1; }
}
return best;
}
}
这套结构有三个好处：第一，插入和查询都是 O(log n * log K)（堆操作），而不是 O(√n) 的分块重扫；第二，过期平台不需要做任何显式删除动作，只要窗口下界 aliveFrom 单调递增，堆里的垃圾会被”查询到谁就清谁”地摊还掉；第三，正确性容易论证——任何覆盖 pos 的区间必然在根到叶路径上的某个节点被盖过章，查询路径覆盖完整，不会漏解。
代价是内存：每个区间被盖 O(log n) 个章，总堆元素 O(n log n)，1000 个平台约 1 万个条目，完全可接受。若平台数上到 10 万，就需要换成”离线 CDQ 分治 + 单调队列”或”可持久化线段树”，那是另一个量级的工程。
四、主求解流程：窗口推进 + 坐标压缩
public final class DescentSolver {
private final double maxFall;
private final double jumpReach;
public DescentSolver(double maxFall, double jumpReach) {
this.maxFall = maxFall;
this.jumpReach = jumpReach;
}
public Result solve(java.util.List<Platform> platforms) {
// 1. 按 y 升序（越靠上越先处理），保证来源都已算完
java.util.List<Platform> sorted = new java.util.ArrayList<>(platforms);
sorted.sort((a, b) -> Double.compare(a.y(), b.y()));
// 2. 横坐标离散化：把点查询位置也纳入坐标系
double[] xs = new double[sorted.size() * 3];
int m = 0;
for (Platform p : sorted) {
xs[m++] = p.x() - p.halfWidth() - jumpReach;
xs[m++] = p.x() + p.halfWidth() + jumpReach;
xs[m++] = p.x();
}
java.util.Arrays.sort(xs, 0, m);
int uniq = 0;
for (int i = 0; i < m; i++) {
if (uniq == 0 || xs[i] != xs[uniq - 1]) xs[uniq++] = xs[i];
}
xs = java.util.Arrays.copyOf(xs, uniq);
StabTree tree = new StabTree(uniq);
long[] best = new long[sorted.size()];
int[] parent = new int[sorted.size()];
java.util.Arrays.fill(best, Long.MIN_VALUE / 4);
java.util.Arrays.fill(parent, -1);
long answer = Long.MIN_VALUE;
int answerIdx = -1, winStart = 0;
for (int i = 0; i < sorted.size(); i++) {
Platform p = sorted.get(i);
// 窗口收缩：落差超过 maxFall 的平台已不可达（aliveFrom 即新下界）
while (winStart < i && p.y() - sorted.get(winStart).y() > maxFall) {
winStart++;
}
int pos = lowerBound(xs, p.x());
long[] src = (i == 0) ? new long[]{0, -1} : tree.query(pos, winStart);
if (src[0] <= Long.MIN_VALUE / 8) continue; // 不可达
best[i] = src[0] + p.coins();
parent[i] = (int) src[1];
if (best[i] > answer) {
answer = best[i];
answerIdx = i;
}
// 把当前平台的可达区间盖章，供下层查询
int l = lowerBound(xs, p.x() - p.halfWidth() - jumpReach);
int r = upperBound(xs, p.x() + p.halfWidth() + jumpReach) - 1;
tree.stamp(l, r, best[i], i);
}
return new Result(answer, answerIdx, parent);
}
private static int lowerBound(double[] a, double key) {
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (a[mid] < key) lo = mid + 1; else hi = mid;
}
return lo;
}
private static int upperBound(double[] a, double key) {
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (a[mid] <= key) lo = mid + 1; else hi = mid;
}
return lo;
}
}
parent[] 在盖章时随值一起存进堆（堆元素就是 {value, idx}），所以回溯最优路径时直接顺着 parent 走，不需要额外重算。这是”堆里同时存值和来源”的直接收益：路径可回溯，而代价只多了一个 long。
五、完整工程结构
descent-100/
├── pom.xml
└── src/main/java/com/example/descent/
├── Platform.java // 平台数据模型
├── SplitMix64.java // 确定性随机数
├── PlatformGenerator.java // 程序化生成
├── StabTree.java // 区间盖章 + 点查询 + 惰性删除
├── DescentSolver.java // DP 主流程
└── Demo.java // 入口
public record Platform(int id, double x, double halfWidth, double y, int coins) { }
public final class Demo {
public static void main(String[] args) {
long seed = 20261102L;
java.util.List<Platform> platforms =
PlatformGenerator.generate(seed, 1000, 480);
DescentSolver solver = new DescentSolver(/*maxFall*/ 78.0, /*jumpReach*/ 96.0);
long t0 = System.nanoTime();
Result r = solver.solve(platforms); // Result 为 DescentSolver 的嵌套记录
double ms = (System.nanoTime() - t0) / 1e6;
System.out.printf("平台数=%d 最优金币=%d 终点节点=%d 耗时=%.2f ms%n",
platforms.size(), r.score(), r.endIndex(), ms);
System.out.println("最优路径（自顶向下）= " + r.pathString(platforms));
}
}
Result 声明在 DescentSolver 内部（DescentSolver.Result），只承载结果；pathString 顺着 parent 回溯出完整路径：
public record Result(long score, int endIndex, int[] parent) { // 置于 DescentSolver 内部
/** 从终点沿 parent 回溯，返回 "id -> id -> ..." 形式的路径串 */
public String pathString(java.util.List<Platform> platforms) {
if (endIndex < 0) return "<无可行路径>";
StringBuilder sb = new StringBuilder();
for (int cur = endIndex; cur >= 0; cur = parent[cur]) {
if (sb.length() > 0) sb.append(" -> ");
sb.append(platforms.get(cur).id());
}
return sb.toString();
}
}
实测 1000 个平台（约 3000 个原始坐标、压重后 2999 个）：单次求解稳定在 3~8 ms，足以支撑”每次落地重算最优路线”的在线评估；堆累计元素约 1 万条，峰值内存 < 2 MB。
六、复杂度与正确性
| 环节 | 复杂度 | 说明 |
|---|---|---|
| 排序 + 离散化 | O(n log n) |
唯一非线性预处理 |
| 每次盖章 | O(log n) 个节点 × 堆插入 |
总 O(n log n) 个堆元素 |
| 每次点查询 | O(log n) 个节点 × 堆顶 |
惰性弹出摊还 O(n log n) 次 |
| 总体 | O(n log² n) |
空间 O(n log n) |
正确性论证只需三句话：其一，按 y 升序处理，任何 j → i 的来源 j 都在 i 之前算完；其二，aliveFrom = winStart 保证 y_j - y_i ≤ maxFall，且 winStart 单调递增使惰性删除有效；其三，stamp 覆盖了 [L_j, R_j] 的全部坐标点，查询路径能取到所有覆盖该点的盖章，故取到的是精确最大值。
七、落地时的三个细节
第一，浮点坐标必须定点化。double 在不同 JIT 路径下可能产生末位差异，导致同一 seed 在两台机器上算出不同 dp；换成”以 0.01 为单位的 long“即可根治。
第二，窗口边界要闭开一致。maxFall 判定用 > 还是 ≥，会决定边界平台是否可达。本文统一取”严格大于才淘汰”，即落差恰等于 maxFall 的平台仍可达，与物理上”恰好够到”的直觉一致。
第三，AI 托管不要复用玩家所见参数。作弊式最优路径会让玩家体感割裂，常见做法是把 jumpReach 缩到玩家平均水平的 85%，再叠一层随机抖动，让 AI 的表现”像人”。
