#P18807. [2027年国家集训队互测]双重反转
[2027年国家集训队互测]双重反转
双重反转
给定一个由 个正整数组成的非降序列 。Alice 和 Bob 进行 轮游戏,初始得分为 0。
每轮,Alice 先选一个从未选过的位置,其值为 ;接着 Bob 可选择使用一次翻转技能,把本轮的 变为 ;最后把该值加入得分。Bob 全局最多使用 次技能。一个位置一旦选了就不能再选,即使数值相同,不同位置也分别计数。
双方知道整个序列且采取最优策略:Alice 最大化终局得分,Bob 最小化。求终局得分。
输入格式
第一行三个整数 。第二行 个整数 ,按非降序给出。
输出格式
一行一个整数,表示最优策略下的终局得分。
样例 1
3 2 2
1 1 2
-2
Alice 可以选两个 1,保证至少得到 。Bob 可以把两次选择都翻转,保证得分不超过 。
样例 2
7 7 2
1 2 3 4 5 6 7
2
每个数都会被选到,Bob 对 6 和 7 使用技能,得分为 。
数据范围
,,。令 。
| 数据分组 | 参考分值 | 上限 | 附加限制 |
|---|---|---|---|
| 1 | 5 | 18 | 无 |
| 2 | 3 | ||
| 3 | 11 | 100 | 无 |
| 4 | 15 | 2000 | |
| 5 | 12 | ||
| 6 | 14 | ||
| 7 | 19 | 无 | |
| 8 | 21 |
本题评测采用50个测试点,每点2分。