#include<iostream>#include<stdio.h>#include<limits.h>using namespace std;int v[305],a[305][305],p,n;int b[305][35];void dp(){ int i,j; for(i=1; i<=n; i++) for(j=1; j<=p; j++) b[i][j]=INT_MAX; for(i=1; i<=n; i++) b[i][1]=a[1][i]; for(i=2; i<=p; i++) for(j=i; j<=n; j++) { for(int k=i; k<=j; k++) if(b[j][i]>b[k][i-1]+a[k+1][j]) b[j][i]=b[k][i-1]+a[k+1][j]; } printf("%dn",b[n][p]);}int main(){int i,j,tmp,k; scanf("%d%d",&n,&p);for(i=1; i<=n; i++)scanf("%d",&v[i]);for(i=1; i<=n; i++)a[i][i]=0; for(tmp=1; tmp<n; tmp++){ for(i=0; i<=n-tmp; i++){j=i+tmp;a[i][j]=a[i+1][j]+v[(i+1+j)/2]-v[i];}}dp();return 0;}
