记录编号	48424	评测结果	AAAAAAAAAA
题目名称	磁性链	最终得分	100
用户昵称	TBK	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2012-11-05 19:01:17	内存使用	6.97 MiB

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <queue>
#include <algorithm>
#define MAXN 0x7fffffff
using namespace std;
int a[1001],b,c,d,f[1001][1001],l,m,n,x;
int main(void)
{
    freopen("linka.in","r",stdin);
    freopen("linka.out","w",stdout);
	scanf("%d%d",&b,&c);
	for (d=1;d<=c;d++) scanf("%d",&a[d]);
	a[c+1]=b+1;
	for(d=1;d<=c;d++) f[d][d]=a[d+1]-a[d-1]-2;
	for(d=1;d<c;d++)
		for(l=1;l+d<=c;l++)
		{
			m=l+d;
			f[l][m]=MAXN;
			for(n=l;n<=m;n++)
			{
				x=f[l][n-1]+f[n+1][m]+a[m+1]-a[l-1]-2;
				if (f[l][m]>x) f[l][m]=x;
			}
		}
	printf("%d",f[1][c]);
	fclose(stdin);
    fclose(stdout);
    return 0;
}