P9824 [ICPC 2020 Shanghai R] Fountains

假设你和你的队友 Mixsx 将参加 Namomo 训练营。Namomo 训练营将持续 $n$ 天。我们将第 $i$ 天命名为第 $i$ 天（$1 \le i \le n$）。第 $i$ 天的费用为 $s_i$。 不幸的是，Namomo 训练营的日程与 Mixsx 的期末考试冲突。Mixsx 在从第 $L$ 天到第 $R$ 天的每一天都有期末考试。他的大学尚未宣布 $L$ 和 $R$ 的确切值，因此我们假设每对整数 $L$ 和 $R$ 满足 $1 \le L \le R \le n$ 的情况将以概率 $1/(n(n+1)/2)$ 被选择。他决定参加所有考试，因此将从第 $L$ 天到第 $R$ 天缺席 Namomo 训练营。在这种情况下，他的损失将是 $\sum_{i=L}^R s_i$。 作为 Mixsx 的队友，你希望 Mixsx 放弃他的期末考试并回到 Namomo 训练营。在 $L$ 和 $R$ 公布之前，你可以准备 $k$ 个计划。在第 $i$ 个计划中（$1 \le i \le k$），你每天从第 $l_i$ 天到第 $r_i$ 天关闭他的大学的电源。你可以选择 $l_i$ 和 $r_i$ 的值，只要它们是满足 $1 \le l_i \le r_i \le n$ 的两个整数。 一旦 $L$ 和 $R$ 被宣布，你可以选择一个计划 $x$（$1 \le x \le k$），使得 $L \le l_x \le r_x \le R$。然后 Mixsx 将在从第 $l_x$ 天到第 $r_x$ 天的每一天回到 Namomo 训练营。在这种情况下，他的损失变为 $\sum_{i=L}^R s_i - \sum_{i=l_x}^{r_x} s_i$。你将选择一个计划以最小化 Mixsx 的损失。如果没有计划 $x$ 满足 $L \le l_x \le r_x \le R$，Mixsx 将正常参加他的期末考试，他的损失是 $\sum_{i=L}^R s_i$。 请计算如果你选择 $k$ 个计划最优地，Mixsx 的最小可能期望损失 $ans_k$。输出每个从 $1$ 到 $n(n+1)/2$ 的 $k$ 的 $ans_k \cdot n(n+1)/2$。 形式上，给定一个 $n$ 个数字 $s_i$ 的列表（$1 \leq i \leq n$），定义损失函数 $C(L, R) = \sum_{i=L}^R s_i$。给定一个整数 $k$（$1 \leq k \leq n(n+1)/2$），你应该选择 $2k$ 个整数 $l_1, \ldots, l_k, r_1, \ldots, r_k$ 满足对于所有 $1 \leq i \leq k$，$1 \le l_i \le r_i \le n$，使得 $$\sum_{1 \leq L \leq R \leq n} \left[C(L, R) - \max_{1 \le i \le k, L \leq l_i \leq r_i \leq R} C(l_i, r_i) \right]$$ 被最小化。（如果没有 $i$ 满足 $1 \le i \le k$ 且 $L \leq l_i \leq r_i \leq R$，则 $\max_{1 \le i \le k, L \leq l_i \leq r_i \leq R} C(l_i, r_i)$ 定义为 $0$。）输出每个整数 $k$ 在 $[1, n(n+1)/2]$ 中的最小化值。

第一行包含一个整数 $n~(1 \leq n \leq 9)$。第二行包含 $n$ 个用空格分隔的整数 $s_i~(1 \leq s_i \leq 10^9)$。

输出包含 $n(n+1)/2$ 个整数，每个整数占一行，表示当 $k = 1, \ldots, n(n+1)/2$ 时的期望值乘以 $n(n+1)/2$。可以证明结果总是整数。

对于第一个测试用例，我们只需要考虑 $k = 1$ 的情况。我们只能选择 $l_1 = r_1 = 1$。然后期望损失是 $C(1, 1) - C(1, 1) = 0$，结果是 $0 \times 1 \times (2) / 2 = 0$。 对于第三个测试用例，考虑 $k = 3$ 的情况。我们选择 $l_1 = r_1 = 1$，$l_2 = r_2 = 3$ 和 $l_3 = 1, r_3 = 3$。期望损失是 $2$。结果是 $2 \times 6 = 12$。 题面翻译由 ChatGPT-4o 提供。