> 好像没问题啊，我查了好几次啦
> 
> #include <stdio.h>
> #include <string.h>
> int n,m;
> int x[301];
> void main()
> {
> 	int i,j,k,l,tm;
> 	int p[301][301],q[301][31];
> 	////p[i][j] 表示村庄i到j间修一个邮局的最小花费。
> 	////q[i][j] 表示前i个村庄修j个邮局的最小花费
> 	scanf("%d%d",&n,&m);
> 	memset(q,0,sizeof(q));
> 	for(i=0;i<n;i++)
> 		scanf("%d",&x[i]);
> 	memset(p,0,sizeof(p));
> 	for(i=0;i<n;i++)
> 		for(j=i+1;j<n;j++)
> 		{
> 			l = i+(j-i)/2;
> 			for(k=i;k<l;k++)
> 				p[i][j] += (x[l]-x[i]);
                             ~~~~~~~~~~~~~~~~~~~~~~~~~x[k]~~~~~~~~~~~
> 			for(k=l+1;k<=j;k++)
> 				p[i][j] += (x[k]-x[l]);
> 		}
> 	for(i=0;i<n;i++)
> 		q[i][1] = p[0][i];
> 	for(i=0;i<n;i++)
> 		for(j=2;j<=m;j++)
> 		{
> 			q[i][j] = 2000000000;
> 			for(k=j-2;k<i;k++)
> 			{
> 				tm = q[k][j-1] + p[k+1][i];
> 				if(tm<q[i][j])
> 					q[i][j] = tm;
> 			}
> 		}
> 		printf("%d\n",q[n-1][m]);
> }

• 这种方法好慢啊 有没有什么好的方法? (73) alpc04 2005-12-14 00:50:47