题目详情题解（0）讨论（0）提交记录（0）

AT_abc303_g.[ABC303G] Bags Game

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 NN 个袋子从左到右排成一列，第 ii 个袋子里有 xix_i 日元。

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

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

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

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

输入格式

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

N A B C D x1 x2 … xNN\ A\ B\ C\ D\ x_1\ x_2\ \ldots\ x_N

输出格式

请输出答案。

输入输出样例

  • 输入#1

    5 10 2 1000000000 1
1 100 1 1 1

    输出#1

    90

  • 输入#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

说明/提示

限制条件

  • 1≤N≤30001 \leq N \leq 3000
  • 1≤xi≤1091 \leq x_i \leq 10^9
  • 1≤A,C≤1091 \leq A, C \leq 10^9
  • 1≤B,D≤N1 \leq B, D \leq N
  • 输入均为整数

样例解释 1

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

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页