Source Code

Problem: 1160  User: yzhw 
Memory: 788K  Time: 0MS 
Language: GCC  Result: Accepted 

Source Code 
# include <stdio.h>
# include <string.h>
# include <math.h>
int n,m;
int data[302],len1[302][302],dp[32][302],path[32][302];
int main()
{
	int i,j,k;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++)
		scanf("%d",&data[i]);
	for(i=1;i<n;i++)
	{
		len1[i][i+1]=abs(data[i+1]-data[i]);
		len1[i][i]=0;
	}
	len1[n][n]=0;
	for(i=2;i<=n;i++)
		for(j=1;j<=n;j++)
			if(j+i<=n)
			{
				int mid=j+i/2;
				len1[j][j+i]=len1[j+1][j+i-1]+abs(data[j]-data[mid])+abs(data[j+i]-data[mid]);
			}

	for(i=1;i<=n;i++)
		dp[1][i]=len1[1][i],path[1][i]=1;
	for(i=2;i<=m;i++)
	{
		j=n;
		dp[i][j]=999999;
		for(k=path[i-1][j];k<j;k++)
			if(dp[i-1][k]+len1[k+1][j]<dp[i][j])
				dp[i][j]=dp[i-1][k]+len1[k+1][j],path[i][j]=k;
		for(j=n-1;j>i;j--)
		{
			dp[i][j]=999999;
			for(k=path[i-1][j];k<=path[i][j+1];k++)
				if(dp[i-1][k]+len1[k+1][j]<dp[i][j])
					dp[i][j]=dp[i-1][k]+len1[k+1][j],path[i][j]=k;
		}
	}
	printf("%d\n",dp[m][n]);
}