记录编号	29993	评测结果	AAAWAAAAAA
题目名称	238.[POI 1999] 地图着色	最终得分	90
用户昵称	Makazeu	是否通过	未通过
代码语言	C++	运行时间	0.772 s
提交时间	2011-10-27 09:22:51	内存使用	22.34 MiB

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int MAXN=2000000000;
int N,M;
int Map[3001];
int F[3001][3001];
int Num[3001][3001];

int cmp(const void *a,const void *b)
{
	return *(int *)a-*(int *)b;
}


void init()
{
	cin>>N>>M;
	for (int i=1;i<=N;i++)
		cin>>Map[i];
	qsort(Map+1,N,sizeof(Map[0]),cmp);
	for (int i=0;i<=N;i++)
	{
		for (int j=0;j<=M;j++)
		{
			F[i][j]=MAXN;
		}
	}
	F[0][0]=0;
	for (int j=1;j<=N;j++)
	{
		Num[j][j]=0;
		for (int i=j-1;i>=1;i--)
		{
			Num[i][j]=Num[i+1][j]+(Map[(i+j+1)/2]-Map[i]);
		}
	}
	return;
}

void DP()
{
	for (int i=1;i<=N;i++)
	{
		for (int j=1;j<=M;j++)
		{
			for (int k=0;k<=i-1;k++)
			{
				if (F[k][j-1]+Num[k+1][i] < F[i][j])
					F[i][j]=F[k][j-1]+Num[k+1][i];
			}
		}
	}
	cout<<F[N][M]<<endl;
}

int main()
{
	freopen("map.in","r",stdin);
	freopen("map.out","w",stdout);
	init();
	DP();
	return 0;
}