记录编号	39339	评测结果	AAAAAAAAAA
题目名称	磁性链	最终得分	100
用户昵称	ZhouHang	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2012-07-09 14:21:18	内存使用	0.60 MiB

/**
*Prob	: linka
*Data	: 2012-7-9
*Sol	: dp+四边形不等式
*/

#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

#define MaxN 1100
#define MaxQ 200

using namespace std;

int n,q;
int a[MaxN],s[MaxN];
int f[MaxQ][MaxQ];
int g[MaxQ][MaxQ];

int main()
{
	freopen("linka.in","r",stdin);
	freopen("linka.out","w",stdout);
	
	scanf("%d%d",&n,&q);
	for (int i=1; i<=q; i++)
		scanf("%d",&a[i]);
	sort(a+1,a+1+q);
	
	a[0] = 0;
	for (int i=1; i<=q; i++)
		s[i] = a[i] - a[i-1] -1;
	s[q+1] = n-a[q];
	for (int i=1; i<=q+1; i++)
		s[i] += s[i-1];
	
	memset(f,127,sizeof(f));
	for (int i=1; i<=q+1; i++) {
		g[i][i] = i;
		f[i][i] = 0;
	}
	for (int i=q+1; i>=1; i--)
	 for (int j=i+1; j<=q+1; j++)
	  for (int k=g[i][j-1]; k<=g[i+1][j]; k++)
	  {
		int tmp = f[i][k]+f[k+1][j]+(s[j]-s[i-1])+(j-i-1);
		if (tmp<f[i][j]) {
			g[i][j] = k;
			f[i][j] = tmp;
		}
	  }
	
	printf("%d",f[1][q+1]);
	
	fclose(stdin); fclose(stdout);
	return 0;
}