感觉很水的一道题，一眼就秒了。

对于成环的题目，首先考虑破环为链，然后我们想怎么快速处理区间贡献。

设 $sum1_i=\sum_{j=1}^i r_i$，$sum2_i=\sum_{j=1}^i r_i\times i$。

则区间贡献 $f_{l,r}=sum2_r-sum2_l-(sum1_r-sum1_l)\times l$。

然后发现 $f_{l,r}$ 满足四边形不等式，证明：设 $a<b<c<d$，则：

$$(f_{a,d}+f_{b,c})-(f_{a,c}+f_{a,d})=$$ $$(sum2_d-sum2_a-(sum1_d-sum1_a)\times a+(sum2_c-sum2_b-(sum1_c-sum1_b)\times b)-$$$$(sum2_c-sum2_a-(sum1_c-sum1_a)\times a+(sum2_d-sum2_b-(sum1_d-sum1_b)\times b)=$$$$(-sum1_d\times a-sum1_c\times b)-(-sum1_d\times b-sum1_c\times a)=$$$$a\times (sum1_c-sum1_d)+b\times(sum1_d-sum1_c)=(sum1_d-sum1_c)(b-a)>0$$

所以可以使用决策单调性优化，复杂度 $O(nk\log n)$，代码如下：

#include<bits/stdc++.h>
using namespace std;
#define N 1005
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
int n,k,ans=INF,r[N],a[N],dp[10][N],sum1[N],sum2[N];
int calc(int l,int r){
	return sum2[r]-sum2[l]-(sum1[r]-sum1[l])*l;
}
void solve(int now,int l,int r,int pl,int pr){
	if(l>r)	return;
	int mid=(l+r)>>1,pos;dp[now][mid]=INF;
	for(int i=pl;i<=min(pr,mid);i++){
		int tmp=dp[now-1][i-1]+calc(i,mid);
		if(tmp<dp[now][mid])  dp[now][mid]=tmp,pos=i;
	}
	solve(now,l,mid-1,pl,pos),solve(now,mid+1,r,pos,pr);
}
void work(){
    for(int i=1;i<=n;i++)  sum1[i]=sum1[i-1]+a[i];
    for(int i=1;i<=n;i++)  sum2[i]=sum2[i-1]+a[i]*i;
    for(int i=1;i<=k;i++)  solve(i,1,n,1,n);
    ans=min(ans,dp[k][n]);
}
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)  scanf("%lld",r+i);
    for(int i=1;i<=n;i++){
        int cnt=0;
        for(int j=i;j<=n;j++)  a[++cnt]=r[j];
        for(int j=1;j<i;j++)   a[++cnt]=r[j];
        fill(dp[0]+1,dp[0]+n+1,INF),work();
    }
    printf("%lld\n",ans);
}