CF1290A Mind Control

你和你的 $n-1$ 个朋友发现了一个整数数组 $a_1, a_2, \dots, a_n$。你们决定按如下方式分配这个数组：所有 $n$ 个人按某个顺序排成一队。每分钟，队首的人可以选择数组的第一个或最后一个元素，将其移除并据为己有。然后他离开队伍，队伍中的下一个人继续这个过程。 你在队伍中的第 $m$ 个位置。在过程开始前，你可以选择至多 $k$ 个不同的人，并说服他们在轮到自己时无论数组中元素是什么，都始终选择第一个或最后一个元素（每个人可以单独选择，不必都一样）。一旦过程开始，你不能再说服其他人，也不能更改已说服的人的选择。 假设你总是做出最优选择。请问，无论你未能控制的朋友如何选择，你能保证自己拿到的元素至少为多少？即，求最大的整数 $x$，使得无论其他人如何选择，你都能保证拿到的元素 $\geq x$。 请注意，你未能控制的朋友可以任意选择，他们不一定会拿最大的元素。

输入包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个用空格分隔的整数 $n$、$m$ 和 $k$（$1 \leq m \leq n \leq 3500$，$0 \leq k \leq n-1$），分别表示数组的元素个数、你在队伍中的位置以及你可以控制的人数。 每个测试用例的第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），表示数组的元素。 保证所有测试用例中 $n$ 的总和不超过 $3500$。

对于每个测试用例，输出一个整数，表示你能保证拿到的最大元素值。

在第一个测试用例中，一种最优策略是强制第一个人拿最后一个元素，第二个人拿第一个元素。 - 第一个人会拿最后一个元素（$5$），因为你强制他拿最后一个。此时剩下的数组为 $[2, 9, 2, 3, 8]$； - 第二个人会拿第一个元素（$2$），因为你强制他拿第一个。此时剩下的数组为 $[9, 2, 3, 8]$； - 如果第三个人选择拿第一个元素（$9$），轮到你时剩下 $[2, 3, 8]$，你会拿到 $8$（最后一个元素）； - 如果第三个人选择拿最后一个元素（$8$），轮到你时剩下 $[9, 2, 3]$，你会拿到 $9$（第一个元素）。 因此，这种策略能保证你至少拿到 $8$。可以证明不存在能保证你至少拿到 $9$ 的策略，所以答案是 $8$。 在第二个测试用例中，一种最优策略是强制第一个人拿第一个元素。此时，最坏情况下第二和第三个人都拿第一个元素，你最终会拿到 $4$。 由 ChatGPT 4.1 翻译