103036: [Atcoder]ABC303 G - Bags Game
Description
Score : $550$ points
Problem Statement
$N$ bags are arranged in a row. The $i$-th bag contains $x_i$ yen (the currency in Japan).
Takahashi and Aoki, who have sufficient money, take alternating turns to perform the following action:
- choose one of the following three actions and perform it.
- choose the leftmost or rightmost bag and take it.
- pay $A$ yen to Snuke. Then, repeat the following action $\min(B,n)$ times (where $n$ is the number of the remaining bags): choose the leftmost or rightmost bag and take it.
- pay $C$ yen to Snuke. Then, repeat the following action $\min(D,n)$ times (where $n$ is the number of the remaining bags): choose the leftmost or rightmost bag and take it.
When all the bags are taken, Takahashi's benefit is defined by "(total amount of money in the bags that Takahashi took) - (total amount of money that Takahashi paid to snuke)"; let this amount be $X$ yen. We similarly define Aoki's benefit, denoting the amount by $Y$ yen.
Find $X-Y$ if Takahashi and Aoki make optimal moves to respectively maximize and minimize $X-Y$.
Constraints
- $1 \leq N \leq 3000$
- $1 \leq x_i \leq 10^9$
- $1 \leq A,C \leq 10^9$
- $1 \leq B,D \leq N$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A$ $B$ $C$ $D$ $x_1$ $x_2$ $\ldots$ $x_N$
Output
Print the answer.
Sample Input 1
5 10 2 1000000000 1 1 100 1 1 1
Sample Output 1
90
If Takahashi and Aoki make optimal moves, it ends up being $X=92$ and $Y=2$.
Sample Input 2
10 45 3 55 4 5 10 15 20 25 30 35 40 45 50
Sample Output 2
85
Sample Input 3
15 796265 10 165794055 1 18804175 185937909 1934689 18341 68370722 1653 1 2514380 31381214 905 754483 11 5877098 232 31600
Sample Output 3
302361955
Input
题意翻译
Takahashi（先手）和 Aoki（后手）在玩游戏。他们有无限的钱，从左到右一共有 $N$ 个物品，第 $i$ 个价值 $x_i$，两个人轮流操作，每次轮到的一个人可以做 $3$ 种操作之一（假设还剩下 $n$ 个物品）。 - 拿走最左边或者最右边的物品。 - 付给 Snuke $A$ 块钱，然后重复以下操作 $\min(B,n)$ 次：拿走最左边或者最右边的物品。 - 付给 Snuke $C$ 块钱，然后重复以下操作 $\min(D,n)$ 次：拿走最左边或者最右边的物品。 定义一个人的最大收益是拿到的所有东西的价值之和减去付给 Snuke 的钱数。 请问如果 $2$ 个人都使用最优策略，使得自身的收益减去对方的收益尽量的大，那么最终 Takahashi 的收益减去 Aoki 的收益会是多少？ - $1\le B,D\le N\le 3000,A,C\le 10^9$Output
分数：$550$ 分
问题描述
$N$ 个袋子排成一排。第 $i$ 个袋子装有 $x_i$ 日元（日本的货币单位）。
有足够资金的高桥和青木轮流执行以下操作：
- 从以下三种操作中选择一种并执行：
- 选择最左边或最右边的袋子并取走。
- 向杉本支付 $A$ 日元。然后，重复以下操作 $\min(B,n)$ 次（其中 $n$ 是剩余袋子的数量）：选择最左边或最右边的袋子并取走。
- 向杉本支付 $C$ 日元。然后，重复以下操作 $\min(D,n)$ 次（其中 $n$ 是剩余袋子的数量）：选择最左边或最右边的袋子并取走。
当所有袋子都被取走时，高桥的收益定义为“（高桥取走的袋子中总金额）-（高桥支付给杉本的总金额）”；这个金额为 $X$ 日元。我们同样定义青木的收益，用 $Y$ 日元表示。
如果高桥和青木分别采取最佳行动来最大化和最小化 $X-Y$，求 $X-Y$。
约束条件
- $1 \leq N \leq 3000$
- $1 \leq x_i \leq 10^9$
- $1 \leq A,C \leq 10^9$
- $1 \leq B,D \leq N$
- 输入中的所有值都是整数。
输入
输入通过标准输入给出以下格式：
$N$ $A$ $B$ $C$ $D$ $x_1$ $x_2$ $\ldots$ $x_N$
输出
打印答案。
样例输入 1
5 10 2 1000000000 1 1 100 1 1 1
样例输出 1
90
如果高桥和青木采取最佳行动，最终结果为 $X=92$，$Y=2$。
样例输入 2
10 45 3 55 4 5 10 15 20 25 30 35 40 45 50
样例输出 2
85
样例输入 3
15 796265 10 165794055 1 18804175 185937909 1934689 18341 68370722 1653 1 2514380 31381214 905 754483 11 5877098 232 31600
样例输出 3
302361955