#P9602. 博弈

    ID: 6214 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高零和博弈区间 DP不变量分析线性 DP

博弈

题目描述

visit_world 最近在研究 Game theory,他设计了一个游戏,邀请他的好朋友 A 和 B 来玩。

游戏在一个长为 NN 的整数序列 {ai}\left\{a_{i}\right\} 上进行,A 和 B 轮流操作,由 A 先手。每次操作是指选择序列最左 / 最右边的元素,并删掉它。

游戏一直进行,直到剩下一个元素 xx,我们定义这次游戏的输出为 xx。A 想让输出尽可能大,B 想让它尽可能小。

但是,就在他们开始玩游戏之前,B 突然接到了一个女朋友的电话,此时 A 就有时间对序列动手脚了。具体来说,A 可以在游戏开始之前先执行恰好 KK 次操作,得到一个对自己更有利的局面(当然, 游戏开始之后仍然是 A 先手)。

现在,问 A 和 B 都按照最优策略玩游戏,游戏的输出值会是多少。

特别地,如果输入的 K=−1K=-1,这表示你需要对 K=0∼N−1K=0 \sim N-1 都计算答案。

输入格式

第一行两个整数 N,KN, K,意义如题目描述。

第二行 NN 个非负整数, 描述序列 {ai}\left\{a_{i}\right\}。

输出格式

若 K≥0K \geq 0,输出一行一个整数,表示答案。

若 K=−1K=-1,输出一行 NN 个整数,第 ii 个数表示 KK 取 i−1i-1 时的答案。

样例

5 1
1 2 4 5 3
5

A 在游戏开始之前删掉 11,并在第一轮中删掉 22。

此时,无论 B 删 33 或者 44,A 就删掉另一个并保留 55。

5 2
1 2 4 5 3
4

游戏的最后一次操作不是由 A\mathrm{A} 执行, 故输出无法取到最大值 55。

数据范围

对 100%100 \% 的数据,2≤N≤2×1052 \leq N \leq 2 \times 10^{5},−1≤K≤N−1-1 \leq K \leq N-1,0≤ai≤1090 \leq a_{i} \leq 10^{9}。

  • 对于 1515 分的数据,N≤300N \leq 300。
  • 对于另外 2020 分的数据, N≤2000N \leq 2000。
  • 对于另外 1010 分的数据,保证 K=0K=0。
  • 对于另外 2020 分的数据,保证 K≥0K \geq 0。
  • 对于另外 3535 分的数据,无特殊限制。