1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4

 5 const int N=510,M=510;

 6 int a[N],s[N],f[N][M],dis[N][N];

 7

 8 int mmin(int x,int y) {return x<y?x:y;}

 9 int main()

10 {

11     int n,m;

12     scanf("%d%d",&n,&m);

13     s[1]=0;

14     for (int i=2;i<=n;i++)

15     {

16       scanf("%d",&a[i]);

17       s[i]=s[i-1]+a[i];//=1到i的距离

18     }

19     for (int l=1;l<=n;l++)

20      for (int r=l;r<=n;r++)

21      {

22        int mid=(l+r)>>1;

23        dis[l][r]=0;

24        for (int k=l;k<mid;k++)

25          dis[l][r]+=s[mid]-s[k];

26        for (int k=mid+1;k<=r;k++)

27          dis[l][r]+=s[k]-s[mid];

28      }

29     memset(f,63,sizeof(f));

30     f[0][0]=0;

31     for (int i=1;i<=n;i++)

32      for (int j=1;j<=m;j++)

33      {

34       if (j>i) {f[i][j]=0;continue;}

35       for (int k=j-1;k<i;k++)

36         f[i][j]=mmin(f[i][j],f[k][j-1]+dis[k+1][i]);

37      }

38     printf("%d\n",f[n][m]);

39     return 0;

40 }