题解：P14611 [NWRRC 2025] Lucky Number Theory

SafariMo · 2025-12-01 22:45:53 · 题解

先考虑 d = 1 的情况。

记 f_{n , k} 表示剩下 n 次投掷，k 次结算的答案。

考虑到只有两种决策：

• 仅投掷，即 f_{n - 1 , k}，记为 A，实际收益为 A + x。
• 投掷加结算，即 f_{n - 1, k - 1} + 1，记为 B。

记 c = B - A。

• 如果 c \leq 0，那显然仅投掷，f_{n, k} = A + 0.5。
• 如果 c \geq 1，显然仅投掷加结算，f_{n , k} = B。
• 否则为 \max(x + A , B) 的平均值，且分界点在 x= c，因此答案为 f_{n , k} = cB + (1 - c)(A + \dfrac{1 + c}{2})。

预处理 f_{n , k}，时间复杂度 \mathcal O(n^2)。

由于仅考虑小数部分，因此 d > 1 的部分是简单的：加上 \dfrac{n(d - 1)}{2} 即可。