记录编号	39332	评测结果	AAAAAAAAAA
题目名称	磁性链	最终得分	100
用户昵称	CC	是否通过	通过
代码语言	C++	运行时间	0.076 s
提交时间	2012-07-09 13:12:15	内存使用	16.33 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
const int INF = 1000000000;
int n,m;
int a[2050],f[2050][2050];
int main() {
	freopen("linka.in","r",stdin);
	freopen("linka.out","w",stdout);
	scanf("%d%d", &n, &m);
	for (int i = 1;i <= m;i++) scanf("%d", &a[i]);
	std::sort(a + 1,a + m + 1);
	a[0] = 0;a[m + 1] = n + 1;
	for (int i = 1;i <= m;i++) f[i][i] = (a[i + 1]- 1) - (a[i - 1] + 1);
	for (int k = 2;k <= m;k++) 
		for (int i = 1;i <= n;i++) {
			int j = i + k - 1,tmp = (a[j + 1] - 1) - (a[i- 1] + 1),o = INF;
			for (int u = i;u <= j;u++) 
				o = std::min(o,f[i][u - 1] + f[u + 1][j]);
			f[i][j] = o + tmp;
		}
	printf("%d\n", f[1][m]);
	return 0;
}