本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
\(\mathcal{Description}\)
Link.
给定序列 \(\{a_n\}\) 和 \(m\)，定义一段区间 \([l,r]\) 的代价为 \((1+\sum_{i=l}^ra_i)^2\)，求把序列划分为恰 \(m\) 段的最小代价和。
\(\mathcal{Solution}\)
忘情（水）二分 owo！
设 WQS 二分当前一段区间的附加代价 \(k\)，考虑 DP，令 \(f(i)\) 为任意划分 \([1,i]\) 的最小代价。记 \(s_i\) 为前缀和，显然：
\[\begin{aligned}
f(i)&=\min_{j\in[0,i)}\{f(j)+(s_i-s_j+1)^2\}+k\\
&=k+(s_i+1)^2+\min_{j\in[0,i)}\{(f(j)+s_j^2-2s_j)-2s_is_j\}
\end{aligned}
\]
注意到斜优的影子，令 \(g(i)=f(i)+s_i^2-2s_i\)，考虑 \(i\) 的两个转移点 \(v<u\)，若 \(u\) 更优，则有：
\[g(u)-2s_is_u<g(v)-2s_is_v\\
\Rightarrow \frac{g(u)-g(v)}{s_u-s_v}<2s_i
\]
于是在 WQS 里面套一个斜优即可。复杂度 \(\mathcal O(n\log\sum_{i=1}^na_i)\)。
\(\mathcal{Code}\)
#include <cstdio>
typedef long long LL;
const int MAXN = 1e5;
const LL INF = 1.1e16;
int n, m, trc[MAXN + 5], que[MAXN + 5];
LL f[MAXN + 5], s[MAXN + 5];
inline int rint () {
int x = 0; char s = getchar ();
for ( ; s < '0' || '9' < s; s = getchar () );
for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );
return x;
}
inline LL g ( const int i ) { return f[i] + s[i] * s[i] - 2 * s[i]; }
inline double slope ( const int i, const int j ) {
return 1.0 * ( g ( i ) - g ( j ) ) / ( s[i] - s[j] );
}
inline bool check ( const LL mid, LL& res ) {
for ( int head, tail, i = head = tail = 1; i <= n; ++ i ) {
for ( ; head < tail && slope ( que[head], que[head + 1] ) < 2 * s[i]; ++ head );
trc[i] = trc[que[head]] + 1;
f[i] = f[que[head]] + ( s[i] - s[que[head]] + 1 ) * ( s[i] - s[que[head]] + 1 ) + mid;
for ( ; head < tail && slope ( que[tail - 1], que[tail] ) > slope ( que[tail], i ); -- tail );
que[++ tail] = i;
}
return trc[n] <= m ? res = f[n] - m * mid, false : true;
}
int main () {
n = rint (), m = rint ();
for ( int i = 1; i <= n; ++ i ) s[i] = s[i - 1] + rint ();
LL l = -INF, r = INF, ans = 0;
while ( l <= r ) {
LL mid = l + r >> 1;
if ( check ( mid, ans ) ) l = mid + 1;
else r = mid - 1;
}
printf ( "%lld\n", ans );
return 0;
}
