洛谷 P3195 [HNOI2008] 玩具装箱#

题目地址：P3195

题目难度：省选/NOI-

P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。

P 教授有编号为 ${1 \cdots n}$ 的 $n$ 件玩具，第 $i$ 件玩具经过压缩后的一维长度为 $C_i$。

为了方便整理，P教授要求：

• 在一个一维容器中的玩具编号是连续的。
• 同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物。形式地说，如果将第 $i$ 件玩具到第 $j$ 个玩具放到一个容器中，那么容器的长度将为 $x=j-i+\sum\limits_{k=i}^{j}C_k$。

制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 $x$，其制作费用为 $(x-L)^2$。其中 $L$ 是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 $L$。但他希望所有容器的总费用最小。

输入格式：

第一行有两个整数，用一个空格隔开，分别代表 $n$ 和 $L$。

第 $2$ 到 第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 件玩具的长度 $C_i$。

输出格式：

输出一行一个整数，代表所有容器的总费用最小是多少。

数据结构：

对于全部的测试点，${1 \leq n \leq 5 \times 10^4}$，${1 \leq L \leq 10^7}$，${1 \leq C_i \leq 10^7}$。

这道题就和《任务安排》一个模子了。设计状态为选前 $i$ 个物品的花费最小值。同样枚举 $i\in[1,n],j\in[0,i-1]$ 然后代入题面长度公式，我们就能得到 $\mathcal O(n^2)$ 的暴力递推公式：dp[i] = min(dp[i], dp[j] + (i - j - 1 + sumC[i] - sumC[j] - L) * (i - j - 1 + sumC[i] - sumC[j] - L))。

对等式进行化简：

考虑到 $L$ 为常数，换元 $L+1=L^\prime$，因此：

发现一组同构，令 $a_k=k+s_k$，再次化简为：

然后拆括号：

我们的斜率需要一个只和循环变量 $i$（以及常数项） 有关的值，对于直线方程，我们不希望斜率里出现任何有关不定项 $j$ 的元素。综上，我们移项得到如下：

此时直线方程的每个要素都很明了了。因为 $c_i$ 为正，就有 $s_i$ 单调递增。根据上式有 $dp_i=b+a_i^2-2a_iL^{\prime}+L^{\prime2}=b+(a_i-L^\prime)^2$，不单调递减，启示我们维护截距 $b$ 的最小值。因此可以直接单调队列维护下凸壳。具体要求如下：

1. 创建一个双端队列来存放凸包上的点的下标
2. 如果队头元素满足 $\frac{(dp_{hh+1}+a_{hh+1}^2)-(dp_{hh}+a_{hh}^2)}{a_{hh+1}-a_{hh}}\leq2(a_i-L^{\prime})$，则弹出队头。因为队头所维护的点的斜率已经失去最优性，在单调递增的斜率意义下不会再被用到。
3. 如果队尾元素满足 $\frac{(dp_{tt}+a_{tt}^2)-(dp_{tt-1}+a_{tt-1}^2)}{a_{tt}-a_{tt-1}}\geq\frac{(dp_i+a_i^2)-(dp_{tt}+a_{tt}^2)}{a_i-a_{tt}}$，则弹出队尾。因为引入的新点 $i$ 使得原先维护的最值点不再最值，类比单调队列中不符合单调性时的弹出操作。

为了避免如上除法操作带来精度影响，故采用交叉相乘法。此时就需要注意相乘结果是否会爆类型。

代码在此

推式子时居然把斜率弄成了 $\frac{\Delta y}{\Delta k}$？？？

洛谷 P3628 [APIO2010] 特别行动队#

题目地址：P3628

题目难度：省选/NOI-

题目来源：APIO  2010

你有一支由 $n$ 名预备役士兵组成的部队，士兵从 $1$ 到 $n$ 编号，你要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如 $(i, i + 1, \cdots i + k)$的序列。所有的队员都应该属于且仅属于一支特别行动队。

编号为 $i$ 的士兵的初始战斗力为 $x_i$ ，一支特别行动队的初始战斗力 $X$ 为队内士兵初始战斗力之和，即 $X = x_i + x_{i+1} + \cdots + x_{i+k}$。

通过长期的观察，你总结出对于一支初始战斗力为 $X$ 的特别行动队，其修正战斗力 $X'= aX^2+bX+c$，其中 $a,~b,~c$ 是已知的系数（$a < 0$）。 作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队的修正战斗力之和最大。试求出这个最大和。

输入格式：

输入的第一行是一个整数 $n$，代表士兵的人数。

输入的第二行有三个用空格隔开的整数，依次代表 $a,~b,~c$，即修正战斗力的系数。

输入的第三行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表编号为 $i$ 的士兵的初始战斗力 $x_i$。

输出格式：

输出一行一个整数，代表最大的所有特别行动队战斗力之和。

数据范围：

对于 ${20\%}$ 的数据，$n \leq 10^3$。

对于 ${50\%}$ 的数据，$n \leq 10^4$

对于 ${100\%}$ 的数据，${1 \leq n \leq 10^6}$，$-5 \leq a \leq -1$，$-10^7 \leq b \leq 10^7$，$-10^7 \leq c \leq 10^7$，${1 \leq x_i \leq 100}$。

写出暴力状态转移方程：dp[i] = max(dp[i], dp[j] + a * X * X + b * X + c)，其中 $X=s_i-s_j,s_k=\sum\limits_{i=1}^{k}x_i$。能拿 $50$ 分，考虑优化。

那么斜率就是 ${2}as_i$、$y$ 就是 $dp_j+as_j^2-bs_j$、截距 $t=dp_i-as_i^2-bs_i$。我们需要最大化 $dp_i$，观察到 $dp_i=t+as_i^2+bs_i$，我们需要让截距最大化。

类比先前推导过的最小化截距的方法，我们可以轻松得出一个结论——截距最大化，维护上凸壳！自己画个图可以知道，我们需要找的最值点就是第一个斜率小于当前直线斜率的点。观察到 ${2as_i}$ 有单调性，因此使用单调队列维护。因为这里的 $a$ 是负数，所以在判断出队时需要变号。

代码在此