记录编号	263743	评测结果	AAAAAAAAAA
题目名称	[IOI 2000]邮局	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2016-05-26 09:36:52	内存使用	1.63 MiB

#include<bits/stdc++.h>
using namespace std;

int Read()
{
	int a = 0, minus = 1;
	char ch = getchar(); 
	while(ch < '0' || ch > '9'){
		ch = getchar();
		if(ch == '-')	minus= -1;
	}
	while(ch >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
		ch = getchar();
	}
	return a * minus;
}

inline int GetMin(const int& a, const int& b)
{
	return a < b ? a : b;
}

inline int Abs(const int& a)
{
	if(a < 0)	return -a;
	return a;
}

int a[4000] = {0}, f[400][50] = {0}, b[400][400] = {0}, d[400][400] = {0};
//f[i][j]:前i个村庄建立j个邮局的最优 
//a[i]:第i个村庄的位置
//b[i][j]:第i个村庄到第j个村庄的距离 
//d[i][j]:第i个村庄到第j个村庄只建立一个邮局的最小距离

int main()
{
	freopen("postoffice.in", "r", stdin);
	freopen("postoffice.out", "w", stdout);
	memset(f, 0x7f, sizeof(f));
	int V = Read(), P = Read();
	for(int i = 1; i <= V; i++)	a[i] = Read();
	for(int i =1; i <= V; i++)
		for(int j = 1; j <= V; j++)
			b[i][j] = Abs(a[j] - a[i]);	
	for(int i = 1; i <= V; i++)
		for(int j = i; j <= V; j++){
			for(int k = i; k <= j; k++){
				d[i][j] += b[(i + j) / 2][k];//初始化?
			}
		}
	for(int i = 1; i <= V; i++)	f[i][1] = d[1][i];	
//	for(int i =1; i <= V; i++)
//		for(int j = 1; j <= V; j++){
//			printf("%d ", d[i][j]);
//			if(j == V)	printf("\n");
//		}		
			 
	for(int i = 1; i <= V; i++)
		for(int j = 1; j <= P; j++)
			for(int k = 1; k < i; k++) 
				f[i][j] =GetMin(f[i][j], f[k][j - 1] + d[k + 1][i]);
			//从k断开,前边建立j-1个邮局,后边建立1个 
	
	int ans = f[V][P];
	printf("%d", f[V][P]);	 
	return 0;
}