✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🤖 内容包含AI辅助生成，题解和代码均经过多轮验证，有问题欢迎评论

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

得物-2026.04.18

这套三题的节奏很顺：第一题利用入栈顺序固定这一点做状态压缩，第二题是标准的“上一天状态 + 已用例外次数”动态规划，第三题则要把视角从单点低洼切到整张图的最终蓄水形态。

第 1 题：小兰的栈内结算汇总

关键不在于直接枚举 步操作序列，而是发现“已经压入了前多少个元素”和“这批元素里哪些已经弹出”就足够描述当前状态。
因为栈顶一定是当前还没弹出的最大下标，所以弹出收益也能直接算出来。

第 2 题：小兰的徒步训练排期

这题的限制只和“昨天有没有爬山”有关，所以状态里不需要记更长的历史。
把“今天休息 / 今天爬山”拆开，再补上“已经用了多少次连续爬山机会”，转移就很直接。

第 3 题：建材堆场的积水分区

这里只找局部低点会漏掉“灌满后连成一片”的情况。
更稳的做法是先用最小堆求出每个位置最终能被水抬到的高度，再把真正有水的位置做连通块统计。

1. 小兰的栈内结算汇总

问题描述

小兰正在顺序处理一批商品。长度为 的数组 记录了商品的基础价值，数组 记录了不同栈深下的结算系数，其中第 个商品的基础价值记为 ，第 个系数记为 。

现在有一个空栈 。处理过程中只允许进行下面两种操作：

• 当数组 里还有没处理的商品时，把当前下标最小、尚未删除的那个商品压入栈 ，并把它从数组 中删除。
• 当栈 非空时，设当前栈内元素个数为 ，栈顶元素的基础价值为 。这时会立刻获得 的结算收益，然后把栈顶元素弹出。

一种合法操作方案必须恰好执行 次操作，并且：

• 执行压栈操作时，数组 里必须还有未处理商品。
• 执行弹栈操作时，栈 必须非空。

一种方案的总收益，定义为其中所有弹栈操作获得收益之和。
请统计所有不同合法操作方案的收益总和。

如果两个方案在某一步选择的操作类型不同，就认为它们是不同方案。

输入格式

• 第一行一个正整数 ，表示数组 和数组 的长度。
• 第二行 个正整数，表示数组 。
• 第三行 个正整数，表示数组 。

输出格式

输出一行一个整数，表示所有不同合法操作方案的收益总和。

样例输入

2
1 2
2 3

样例输出

14

数据范围

• 
• 
• 

题解

直接枚举 步操作序列当然能做，但状态会非常散。
这题真正好用的性质是：压栈顺序完全固定，永远只能按 的顺序进入栈。

1. 状态怎么描述

假设已经把前 个数都“压栈过了”，这时栈里只可能出现这 个数中的一部分。
再用一个二进制掩码 mask 记录“这 个数里哪些已经被弹出”：

• mask 的第 位为 1，表示 已经弹出。
• mask 的第 位为 0，表示 还留在栈里。

于是状态就可以写成 dfs(i, mask)。

因为入栈顺序固定，当前栈顶一定是“前 个元素里下标最大、但还没有弹出的那个元素”。
也就是说，栈顶是谁不需要额外存，直接从 mask 里找最高位的 0 就行。

2. 状态转移

设当前已经弹出的元素个数为 popcnt(mask)，那么当前栈大小就是：

从状态 dfs(i, mask) 出发，有两种选择。

操作一：继续压栈

如果 ，说明还有下一个元素可以压入。
那就直接转移到：

操作二：弹出当前栈顶

如果当前栈非空，也就是 ，就可以弹栈。
栈顶元素是前 个数里还没弹出的最大下标位置，记它的下标为 。
这次弹栈能得到的收益是：

弹完之后，把 mask 中对应位置设为 1，继续递归即可。

3. 记忆化返回什么

对每个状态，记忆化返回两个量：

• ways：从当前状态走到结束，一共有多少种合法后续方案。
• sum：这些后续方案的收益总和。

如果当前弹栈获得的即时收益是 gain，而后继状态返回 (subWays, subSum)，那么这一支对答案的贡献就是：

因为 gain 会加到这条分支的每一种后续方案上。

4. 复杂度

状态总数不超过：

每个状态只做常数次转移，因此总复杂度是：

• 时间复杂度：
• 空间复杂度：

在 的范围内完全可以通过。

参考代码（Python）

import sys
from functools import lru_cache

def input() -> str:
    return sys.stdin.readline().strip()

def solve() -> None:
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    full = (1 << n) - 1

    @lru_cache(None)
    def dfs(i: int, msk: int) -> tuple[int, int]:
        # 前 n 个数都压过并且也都弹完，说明形成了一条完整方案。
        if i == n and msk == full:
            return 1, 0

        ways = 0
        total = 0

        # 当前已经弹出了多少个元素。
        pop = msk.bit_count()
        # 当前栈里还剩多少个元素。
        size = i - pop

        # 选择 1：继续压入下一个元素。
        if i < n:
            sub_w, sub_s = dfs(i + 1, msk)
            ways += sub_w
            total += sub_s

        # 选择 2：弹出当前栈顶。
        if size > 0:
            # 只保留前 i 位，并取其中最高位的 0，这个位置就是当前栈顶。
            ava = ((1 << i) - 1) & (~msk)
            top = ava.bit_length() - 1

            # 当前栈深是 size，对应系数是 b[size - 1]。
            gain = b[size - 1] * a[top]

            sub_w, sub_s = dfs(i, msk | (1 << top))
            ways += sub_w
            total += sub_s + sub_w * gain

        return ways, total

    print(dfs(0, 0)[1])

if __name__ == "_