好像没问题啊，我查了好几次啦

#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]);
			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]);
}

• Re:DP,Why WA, (838) 002 2004-10-01 16:52:11
  • 对不起问个无关的问题： 怎么判断一个图有没有回路啊！急 (0) 002 2004-10-01 16:53:16
    • 深度优先访问，如果访问到已访问的点，就是有回路。 (17) hawk 2004-10-01 16:56:26
• Re:ft,写错了一个变量 (909) lookus 2004-10-01 18:56:10
  • 这种方法好慢啊 有没有什么好的方法? (73) alpc04 2005-12-14 00:50:47
• 能贪心么? 按最大间隔把路分成 p 段 (838) sunmoonstar_love 2006-07-22 12:46:45