Description

Analysis

这个数据范围很显然的要分段程序

K=2

两段越平均越好，直接O(n)扫一遍即可

K=3

三段越平均越好，我们枚举其中一个等分点，调整另一个等分点（这个可以通过指针移动或二分来实现）。然后我们就有了两个等分点。但是这两个等分点的答案不一定是最优的。所以左边的等分点可能向右移一格。这会造成什么后果呢？右边的等分点会向右移动若干格。这个可以二分搞一波，然后整个过程就是O(nlogn)的 （我没打二分直接调整两个等分点向左右偏离一点点取min水过去了，面壁中）

K>3且N<=400

这个数据范围可以dp啦>< 枚举圆环在哪个位置断开 状态很好设，f[i][j]表示前i个位置分了j段的最小值。 写出DP式子，就是 f[i][j]=min(f[k][j−1]+(s[i]−s[k]−avg)2)(k<i) $$f[i][j]=min(f[k][j-1]+(s[i]-s[k]-avg)^2)(k<i)$$ s表示前缀和 O(n3k)$O(n^3k)$，爆炸 一看，嘿嘿嘿，这不是斜率优化标准形式吗，化简一下式子，两个决策k,l，k优于l当且仅当 g(k,l)=F(k,j)−F(l,j)s[k]−s[l]<2∗s[i] $$g(k,l)=/frac{F(k,j)-F(l,j)}{s[k]-s[l]}<2*s[i]$$ 其中定义F(i,j)=f[k][j−1]+s[k]2+2∗avg∗s[k]$F(i,j)=f[k][j-1]+s[k]^2+2*avg*s[k]$ i递增 然后就是裸的斜率优化了，O(n2k)$O(n^2k)$

Code