#include<iostream>
#include<vector>
using namespace std;

#define max 10000000

int main()
{
	int n;//the number of the villege
	int m;//the number of the postoffice
	while(cin>>n>>m)
	{
	if(m==n)
	{
		cout<<'0'<<endl;
		continue;
	}
	int vpos[302];
	int  i, j;
	for(i=0; i<n; i++)
		cin>>vpos[i+1];
	int dis[302][32]={0};
	int cost[302][32]={0};
	for(i=1; i<=n; i++)//the smallest distance between posi ans posj if there just one post office
		for(j=1; j<=n; j++)
			if(i>=j)
				dis[i][j] =0;
			else
				dis[i][j] = dis[i][j-1]+vpos[j]-vpos[(i+j)/2];

	for(i=1; i<=n; i++)
		cost[i][1] = dis[1][i];
	for(i=2; i<=m; i++)
		for(j=i+1; j<=n;  j++)
		{
			int mid;
			cost[j][i] = max;
			for(int t=i-1; t<=j; t++)
			{
				mid = cost[t][i-1] + dis[t+1][j];//cost[n,m]=cost[r,m-1]+dis[r+1,n]
				if(mid<cost[j][i])
					cost[j][i] = mid;//take the smallest distance
			}
		}
	cout<<cost[n][m]<<endl;
	}
	return 0;
}

• Re:为什么总是WA呀? 都是按照解题报告上的方法来的，大侠帮忙看下错哪了，谢谢！！！ (31) 20050503 2007-06-11 21:35:18
• Re:为什么总是WA呀? 都是按照解题报告上的方法来的，大侠帮忙看下错哪了，谢谢！！！ (1059) 00513003 2007-10-26 20:52:29