记录编号	39356	评测结果	AAAAAAAAAA
题目名称	磁性链	最终得分	100
用户昵称	Czb。	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2012-07-09 15:16:26	内存使用	0.34 MiB

#include<stdio.h>
#include<stdlib.h>
 
int n,m,a[101],f[110][110];
 
int min(int a,int b)
{
    return a<b?a:b;
}
 
int dfs(int l,int r)
{
    if(f[l][r])return f[l][r];
    if(l==r)
    {
        f[l][r]=a[r+1]-a[l-1]-2;
        return f[l][r];
    }
	f[l][r]=min(dfs(l+1,r),dfs(l,r-1))+a[r+1]-a[l-1]-2;
    for(int i=l+1;i<r;i++)
    {
        f[l][r]=min(f[l][r],dfs(l,i-1)+dfs(i+1,r)+a[r+1]-a[l-1]-2);
    }
    return f[l][r];
}
 
int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
 
int main()
{
    freopen("linka.in","r",stdin);
    freopen("linka.out","w",stdout);
    int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
    }
    qsort(a+1,m,4,cmp);
    a[++m]=n+1;
    printf("%d\n",dfs(1,m-1));
    return 0;
}