CodeForces – 1495A – Diamond Miner
给定 $2n$ 个点,其中 $n$ 个在 $x$ 轴上,另外 $n$ 个在 $y$ 轴上。现在要求每一个 $x$ 轴上的点与一个 $y$ 轴上的点连线,每个点恰好被连线一次。求所有线段的欧几里得距离之和。
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$.