AT_abc303_g [ABC303G] Bags Game

题目描述

有 $N$ 个袋子从左到右排成一列，第 $i$ 个袋子里有 $x_i$ 日元。

高桥君和青木君都拥有足够多的钱，他们轮流进行操作，高桥君先手。每次操作可以选择以下三种之一：

• 选择并取走最左端或最右端的一个袋子。
• 向すぬけ君支付 $A$ 日元，然后重复 $\min(B, n)$ 次“选择并取走最左端或最右端的一个袋子”的操作（$n$ 为当前剩余袋子的数量）。
• 向すぬけ君支付 $C$ 日元，然后重复 $\min(D, n)$ 次“选择并取走最左端或最右端的一个袋子”的操作（$n$ 为当前剩余袋子的数量）。

当所有袋子都被取走时，高桥君的收益定义为“高桥君取走的所有袋子中金额的总和减去高桥君支付给すぬけ君的总金额”，记为 $X$ 日元。青木君的收益同理，记为 $Y$ 日元。

请计算在两人都采取最优策略的情况下，使 $X-Y$ 最大化的 $X-Y$ 的值。

输入格式

输入从标准输入读入，格式如下：

$N\ A\ B\ C\ D\ x_1\ x_2\ \ldots\ x_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

5 10 2 1000000000 1
1 100 1 1 1

输出 #1

90

输入输出样例 #2

输入 #2

10 45 3 55 4
5 10 15 20 25 30 35 40 45 50

输出 #2

85

输入输出样例 #3

输入 #3

15 796265 10 165794055 1
18804175 185937909 1934689 18341 68370722 1653 1 2514380 31381214 905 754483 11 5877098 232 31600

输出 #3

302361955

说明/提示

限制条件

• $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$
• 输入均为整数

样例解释 1

当高桥君和青木君都采取最优策略时，$X=92,\ Y=2$。

由 ChatGPT 4.1 翻译