当前位置:首页 > Windows程序 > 正文

[bzoj1911][Apio2010]特别行动队

2021-03-12 Windows程序

技术分享

个元素

技术分享

,可以将

技术分享

个元素分成多组,每组的元素编号必须是连续的.

设每组的

技术分享

技术分享

,则每组的价值公式为

技术分享

.

求最大价值和.

Input

输入由三行组成。

第一行包含一个整数,表示士兵的总数.

第二行包含三个整数

技术分享

,价值公式中各项的系数.

第三行包含

技术分享

个用空格分隔的整数

技术分享

.

Output

输出一个整数,,表示最大价值和。

Sample Input

4

-1 10 -20

2 2 3 4

Sample Output

9

HINT

 

技术分享

Solution

技术分享

表示前

技术分享

个的最大价值和,

技术分享

.

这样是

技术分享

的,显然过不了,所以考虑斜率优化.

技术分享

技术分享

时,

技术分享

技术分享

尽量将

技术分享

分离:

技术分享

,

技术分享

技术分享

,

技术分享

.

技术分享

的前提条件是

技术分享

.

整理得,

技术分享

.

温馨提示: 本文由Jm博客推荐,转载请保留链接: https://www.jmwww.net/file/59961.html