#include<stdio.h>
__int64 cost[301][301];
__int64 opt[31][301];
int main()
{
	int i,j,k;
	int n,m;//m是村庄数，n是邮局数。
	long villiage[300];
	scanf("%d%d",&m,&n);
	for(i=1;i<=m;i++)
		scanf("%ld",&villiage[i]);
	for(i=1;i<=m;i++)
		for(j=i;j<=m;j++)
		{
			cost[i][j]=0;
			int mid=(i+j)/2;
			for(k=i;k<=j;k++)
			{
				__int64 distance;
				distance=(villiage[mid]-villiage[k]>0)?(villiage[mid]-villiage[k]):(villiage[k]-villiage[mid]);
				cost[i][j]+=distance;
			}
		}
	for(i=0;i<31;i++)
		for(j=0;j<=300;j++)
			opt[i][j]=3000000;
		opt[0][0]=0;
    for(i=0;i<=n;i++)
		for(j=0;j<=m;j++)
		{
			if(opt[i][j]<3000000)
			for(k=1;k+j<=m;k++)
			{
				if(opt[i+1][k+j]>opt[i][j]+cost[j+1][k+j])
					opt[i+1][k+j]=opt[i][j]+cost[j+1][k+j];
			}
		}
	printf("%I64d\n",opt[n][m]);
	return 0;
}

• Re:为什么runtime error,那位牛人帮我看一下 (13) zhanglongpan 2009-08-02 21:54:32