CF2239B Decidophobia

有 $n$ 个人参加一个圆桌聚会，按照顺时针顺序编号为 $1, 2, 3, \ldots, n$。你准备了一些礼物要分发给他们。 每个人 $i$ 有一个权重 $a_i$ 和一个共同的视野范围 $d$。对于第 $i$ 个人，他的视野包括他顺时针方向的 $d$ 个人和逆时针方向的 $d$ 个人（共计 $2d$ 个人，不包括他自己）。 第 $i$ 个人获得的幸福值按照以下规则计算： - 如果第 $i$ 个人收到了礼物，且在他视野中的 $x$ 个人没有收到礼物，则他会获得 $x \cdot a_i$ 的幸福值。 - 如果第 $i$ 个人没有收到礼物，且在他视野中的 $x$ 个人收到了礼物，则他会损失 $-x \cdot a_i$ 的幸福值。 你的目标是最大化 $n$ 个人幸福值的总和。请你求出这个最大值。

每个测试包含多组数据。第一行输入测试组数 $t$（$1 \le t \le 10^4$）。接下来是每组测试的数据。 每组测试的第一行为两个整数 $n$ 和 $d$（$3 \le n \le 2 \times 10^5$，$1 \le d < \frac{n}{2}$）。 第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^8$），$a_i$ 表示第 $i$ 个人的权重。 保证所有测试组中 $n$ 的总和不超过 $10^6$。

对于每组测试数据，输出一个整数，表示最大化总幸福值后的结果。

在第一个测试用例中，有 3 个人围成一圈。对于每个人 $i$，他的视野范围为 $d=1$，包含他顺时针和逆时针各 1 位邻居。如果第 2 个人收到了礼物，他会因为有 2 个邻居未收礼而获得 $2 \cdot a_2 = 2 \cdot 2 = 4$ 的幸福值。然而，第 1 和第 3 个人因未收礼却有邻居收礼而分别损失幸福值。经过所有可能方案的计算，最大幸福值为 3。 在第二个测试用例中，$n=5, d=1$。最优方案是给第 2、3、5 个人礼物，可以获得最大幸福值 15。 由 ChatGPT 5 翻译