这次的 Leetcode 周赛 (350) 第四题还挺巧妙的

https://leetcode.com/contest/weekly-contest-350/problems/painting-the-walls/

说白了就是：Given two integer arrays cost and time of size n. Choose m <= n indices M from $\{0, 1, ..., n-1\}$, s.t. $\sum_{i \in M} \mathrm{time}_i + m >= n$, while minimizing $\sum_{i \in M} \mathrm{cost}_i$.

其中 $\sum_{i \in M} \mathrm{time}_i + m >= n$ 这个约束，第二项是 $m$ 个 paid painter 的贡献，第一项是在这些 paid painter 工作期间，free painter 可以做的贡献。容易想到它可转化为 $\sum_{i \in M} (\mathrm{time}_i + 1) >= n$，那么把 time 的每个元素 + 1，就化为了原版的「有容量下界限制的背包问题」。

hugify6/19/2023, 7:59:42 PM

Preview:

Cancel

Elsewhere

Colliot replied to 阿里巴巴数学竞赛选错赛道了

弱反射原理 mathbb{P}{M_t ge a} = 2mathbb{P}{B_t ge a}，其中 M_t = sup_{sin[0,t]}B_s 是布朗运动 B_t 在 [0,t] 内达到的最大值。它可以写作mathbb{P}{B_t ge a}=dfrac{1}{2}mathbb{P}{M_t ge a}，这个在直观上很容易理解，因为 B_t ge a 必然有 M_t ge a，而 M_t 第一次到达 a 之后，后续任何点大于或小于 a 的概率都是 1/2。强反射原理给定标准布朗运动 B_t，假设 s 是个停时，那么

begin{equation} B'_t= begin{cases} B_t & text{if } t le s 2B_s-B_t & text{if } t > s end{cases} end{equation}

仍是标准布朗运动。这实际上就是「第一次到达 a 之后，后续任何点大于或小于 a 的概率都是 1/2」的严格表述。所以后者可以推出前者。