1160.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include<iostream>
#include<stdlib.h>
#include<search.h>
#include<cmath>
using namespace std;
long int sub( long int a[], int i, int j)
{
	long int	sum=0;
	for(int k=i;k<=j;k++)
		 sum+=abs(a[k]-a[(i+j)/2]);
	return sum;
}
int  main()
{
	int i, j, k;
	long int m[301][31]={0};
	long int s[301][301]={0};
	long int a[301];
	int v;
	int p;
	cin>>v;
	cin>>p;
	for(i=1;i<=v;i++)	
		cin>>a[i];
	for(i=1;i<=300;i++)
		for(j=1;j<=300;j++)
			s[i][j]=sub(a,i,j);
	for(i=1;i<=v;i++)
		m[i][1]=s[1][i];
	for(j=2;j<=p;j++)
		for(i=j+1;i<=v;i++)
		{
			long int min=s[j][i];
			for(k=j;k<=i-1;k++)
			{
				long temp=m[k][j-1]+s[k+1][i];
				if(temp<min)min=temp;
			}
			m[i][j]=min;
		}
	cout<<m[v][p];
	return 0;


}