AT_abc285_e [ABC285E] Work or Rest

题目描述

高桥君所居住的世界中，一周有 $N$ 天。
一周的天数依次为星期 $1,2,\dots,N$，星期 $N$ 结束后，下一周从星期 $1$ 开始。

作为 ABC 国的国王，高桥君需要为每一天分配“工作日”或“休息日”。这种分配每周都必须相同。此外，必须至少有一天被分配为“休息日”。

在上述条件下，星期 $i$ 的产量通过长度为 $N$ 的数列 $A$ 定义如下：

• 如果星期 $i$ 是“休息日”，则产量为 $0$。
• 如果星期 $i$ 是“工作日”，假设距离它最近的前一个休息日为 $x$ 天前，最近的后一个休息日为 $y$ 天后，则该天的产量为 $A_{\min(x,y)}$。
  • 由于分配每周循环一次，最近的前/后休息日可能属于不同的周。具体请参见样例说明。

请你求出在合理分配的情况下，一周总产量的最大值。
这里一周总产量指的是星期 $1,2,\dots,N$ 的产量之和。

输入格式

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

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

请输出最大的一周总产量，结果为整数。

输入输出样例 #1

输入 #1

7
10 10 1 1 1 1 1

输出 #1

50

输入输出样例 #2

输入 #2

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

输出 #2

5100000000

输入输出样例 #3

输入 #3

20
38 7719 21238 2437 8855 11797 8365 32285 10450 30612 5853 28100 1142 281 20537 15921 8945 26285 2997 14680

输出 #3

236980

说明/提示

限制条件

• 输入均为整数。
• $1\leq N\leq 5000$
• $1\leq A_i\leq 10^9$

样例说明 1

例如，将星期 $2,4$ 分配为“休息日”，其余分配为“工作日”，可以得到一周总产量 $50$，具体如下：

• 星期 $1$：$x=4,y=1$，因此产量为 $A_1=10$。
• 星期 $2$：为“休息日”，产量为 $0$。
• 星期 $3$：$x=1,y=1$，因此产量为 $A_1=10$。
• 星期 $4$：为“休息日”，产量为 $0$。
• 星期 $5$：$x=1,y=4$，因此产量为 $A_1=10$。
• 星期 $6$：$x=2,y=3$，因此产量为 $A_2=10$。
• 星期 $7$：$x=3,y=2$，因此产量为 $A_2=10$。

无法使一周总产量达到 $51$ 或更高。

由 ChatGPT 4.1 翻译