p3534 sol（POI2012 STU）

极值问题考虑二分答案。首先，对于答案 $w$，如果没有 $a_k=0$ 的限制，那么我们只需要满足 $|x_i-x_{i-1}|\le w$。

考虑对序列执行如下操作：

感性理解即可证明这个序列合法且最优，最优指的是元素尽量小。这部分的贡献可以提前算出。

考虑 $k$，那么需要令 $x_i\larr\min(x_i,w\times|i-k|)$，暴力计算这部分的贡献肯定超时。

考虑到 $|x_i-x_{i+1}|\le w$，那么

据此，可得 $x_i>w\times|i-k|$ 的一定是一个区间，而且是一个两端点随 $k$ 增大而增大的区间。动态维护即可。