题意
今天不想简化题面。。。
P 教授要去看奥运，但是他舍不得他的玩具，于是他决定把所有的玩具运到北京。
他使用自己的压缩器进行压缩。这个压缩器可以将任意物品变成一维，再放到一种特殊的一维容器中。P 教授有编号为 $1\dots n$ 的 $n$ 件玩具，玩具经过压缩后会变成一维，第 $i$ 件件玩具压缩后长度为 $C_i$。
为了方便整理，P 教授要求：
- 在一个一维容器中，玩具的编号是连续的；
- 如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物。形式地说，如果要将 $i$ 号玩具到 $j$ 号玩具放到同一个容器中，则容器长度不小于 $x=j-i+\sum_{k=i}^{j}C_k$。
制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 $x$，其制作费用为 $(x-L)^2$，其中 $L$ 是一个常量。
P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 $L$。试求最小费用。
数据范围：$1\le n\le 5\times 10^4$，$1\le L,C_i\le 10^7$
思路
DP : 斜率优化+单调队列
朴素的解法
令$ans[i]$为选到第$i$个玩具时的最小费用, 列出朴素的状态转移方程: $$ ans[i]=\min_{0\le j<i}{(ans[j]+(i-j-1-L+\Sigma_{k=j+1}^iC_k)^2)} $$ 如果$sum[i]=\sum_{j=0}^iC_j$ : $$ ans[i]=\min_{0\le j<i}{(ans[j]+(i-j-1-L+sum[i]-sum[j])^2)} $$ 然后复杂度是$\Omicron(n^2)$, 呜呜呜到底要怎么办呢.
先把式子化简, 令$f[i]=sum[i]+i$ 和 $L’=L+1$, 就有了: $$ ans[i]=\min_{0\le j<i}{(ans[j]+(f[i]-f[j]-L^{\prime})^2)} $$
斜率方程
把和$j$无关的项移到左侧:
$$ ans[i]-(f[i]-L’)^2=\min_{0\le j<i}{\lbrace ans[j]+f[j]^2+2f[j] (L’-f[i])\rbrace} $$
把一次函数的斜截式$y=kx+b$移动得到$y-kx=b$. 发现可以这样表示: $$ \begin{aligned} x_j=&f[j]\\ y_j=&ans[j]+f[j]^2\\ k_i=&-2(L’-f[i])\\ b_i=&ans[i]-(f[i]-L’)^2\\ \end{aligned} $$ 所以转移方程也就是: $$ b_i=\min_{0\le j<i}{(y_j-k_ix_j)} $$ 其实就是求直线最小的截率$b_i$. 显然地, 答案在点集${(x_i, y_i)}$的下凸壳上, 具有决策单调性, 请自行证明.
代码
const int N = 5e4+5;
ll n, L, f[N], ans[N], qu[N], hd, tl;
#define pow2(a) pow(a, 2)
inline double slope(ll x, ll y){
return (double)((ans[y]+pow2(f[y]+L))-(ans[x]+pow2(f[x]+L)))/(2.0*(f[y]-f[x]));
}
int main(){
cin>>n>>L, L++;
for(int i=1, tmp;i<=n;i++) cin>>tmp, f[i]=f[i-1]+tmp+1;
for(int i=1;i<=n;i++){
while(hd<tl&&slope(qu[hd], qu[hd+1])<=f[i]) hd++;
ans[i]=ans[qu[hd]]+pow2(f[i]-f[qu[hd]]-L);
while(hd<tl&&slope(qu[tl], i)<slope(qu[tl-1], qu[tl])) tl--;
qu[++tl]=i;
}
cout<<ans[n]<<endl;
return 0;
}