AT_arc116_f [ARC116F] Deque Game

题目描述

给定 $K$ 个数列。第 $i$ 个数列 $A_i$ 的长度为 $N_i$。

高桥君和青木君将用这些数列进行游戏。直到所有数列都变为长度 $1$，高桥君和青木君轮流进行以下操作：

• 选择一个长度至少为 $2$ 的数列，删除其第一个元素或最后一个元素。

高桥君先手。高桥君希望最大化最后剩下的 $K$ 个元素的总和，青木君则希望最小化该总和。

当双方都采取最优策略时，请输出最后剩下的 $K$ 个元素的总和。

输入格式

输入以如下格式从标准输入给出。

$K$ $N_1$ $A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,N_1}$ $N_2$ $A_{2,1}$ $A_{2,2}$ $\cdots$ $A_{2,N_2}$ $\vdots$ $N_K$ $A_{K,1}$ $A_{K,2}$ $\cdots$ $A_{K,N_K}$

输出格式

输出答案。

样例 1

输入

2
3 1 2 3
2 1 10

输出

12

样例 2

输入

8
1 2
2 1 2
3 1 2 1
4 1 1 1 2
5 1 1 2 2 1
6 2 2 2 2 1 1
7 1 2 1 1 2 2 2
8 2 2 2 1 1 1 1 2

输出

12

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq K \leq 2 \times 10^5$
• $1 \leq N_i$
• $\sum_i N_i \leq 2 \times 10^5$
• $1 \leq A_{i,j} \leq 10^9$

样例说明 1

以下是游戏进行的一种情况：

• 高桥君删除 $A_2$ 的第一个元素。此时各数列为 $A_1 = (1, 2, 3),\ A_2 = (10)$。
• 青木君删除 $A_1$ 的最后一个元素。此时各数列为 $A_1 = (1, 2),\ A_2 = (10)$。
• 高桥君删除 $A_1$ 的第一个元素。此时各数列为 $A_1 = (2),\ A_2 = (10)$。

所有数列长度都变为 $1$，游戏结束。此时最后剩下的 $K$ 个元素的总和为 $12$。注意，这种游戏过程不一定是双方的最优策略。

由 ChatGPT 4.1 翻译