CF590D Top Secret Task

在 Zuev 上校指挥下的一个绝密军事基地即将迎来国防部的检阅。根据条例，每个绝密军事基地都必须包括一个绝密部队，这个部队应该……嗯，具体应该做什么我们不能告诉你，毕竟它是绝密部队。问题在于，出于某些原因，Zuev 上校的基地缺少了这个绝密部队。 上校决定立刻解决这个问题，并命令基地的全部 $n$ 名士兵站成一排。Zuev 知道，从左往右数第 $i$ 名士兵的健谈度为 $q_i$。Zuev 想用排在最左边的 $k$ 名士兵组建这个绝密部队，因此他希望这 $k$ 名士兵的健谈度总和尽可能小（因为部队需要保持绝密）。为了达到这个目的，他可以选择一对相邻的士兵交换他们的位置。他最多只能执行 $s$ 次这样的交换。注意，任何士兵都可以参与任意多次交换。 请你帮助 Zuev 上校，求出通过不超过 $s$ 次相邻交换，可获得的最小的前 $k$ 名士兵健谈度之和。

输入的第一行包含三个正整数 $n$、$k$、$s$（$1 \leq k \leq n \leq 150$，$1 \leq s \leq 10^{9}$）——表示士兵数量、绝密部队的规模以及最多允许的相邻交换次数。 第二行包含 $n$ 个整数 $q_i$（$1 \leq q_i \leq 1000000$），表示士兵按从左到右排列时的健谈度。

输出一个整数，表示可获得的最小的前 $k$ 名士兵健谈度之和。

在第一个样例中，上校需要把第二个和第三个士兵交换，他实际上并不需要剩余的交换次数。交换后的士兵顺序为 $(2,1,4)$。绝密部队的最小健谈度之和为 $3$。 在第二个样例中，上校可按以下顺序进行交换： 1. $(10,1,6,2,5)$ — 将第 $4$、$5$ 号交换 2. $(10,1,2,6,5)$ — 将第 $3$、$4$ 号交换 交换后的士兵顺序为 $(10,1,2,5,6)$。 最小可能的健谈度之和为 $18$。 由 ChatGPT 5 翻译