标签: 斜率优化

3 篇文章

Luogu – P3628 – [APIO2010]特别行动队
给定一个长度为 $n$ 的序列,每个元素有权值 $x_i$,现在要将序列分割为若干段,每段中元素连续。设 $s_i$ 表示前缀和,即 $s_i=\sum_{j=1}^{i}{x_j}$,那么对于每段 $[l, r]$,代价为: $$ a(s_{i}-s_{j-1})^2+b(s_i-s_{j-1})+c $$ 其中 $a, b, c$ 为题目给定的常数。整个序列的代价为每段代价之和。
求序列的代价最大值。
$1\leq n\leq 10^6, -5\leq a\leq -1, -{10}^7\leq b, c\leq 10^7, 1\leq x_i\leq 100$.