记录编号	48319	评测结果	AAAAAAAAAA
题目名称	奇怪的监狱	最终得分	100
用户昵称	fflyt	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2012-11-05 15:30:06	内存使用	9.76 MiB

//from auto
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int MAXN=1011;
const int INF=(~0u>>2)-2;
int N,M,Num[MAXN],T,Ans;
int F[MAXN][MAXN],A[MAXN],Sum[MAXN][MAXN]={0};
      
inline void init()
{
    scanf("%d %d\n",&N,&M);
    for(int i=1;i<=M;i++) 
        scanf("%d",&Num[i]);
    sort(Num+1,Num+1+M);
    Num[0]=0,Num[M+1]=N+1;
	T=M+1;
	
    for(int i=1;i<=M+1;i++){
        if((Num[i]-1)<(Num[i-1]+1)) continue;
        A[i]=Num[i]-Num[i-1]-1;
    }
    for(int i=1;i<=T;i++)
        for(int j=1;j<=T;j++)
            F[i][j]=INF;
		
    for(int i=1;i<=T;i++){
        F[i][i]=0,Sum[i][i]=A[i];
        for(int j=i+1;j<=T;j++)
            Sum[i][j]=Sum[i][j-1]+A[j];
    }
}
      
inline int Min(int a,int b) {return a<b?a:b;}

inline void dp()
{
    for(int len=2;len<=T;len++){
        for(int i=1;i<=T-len+1;i++){
            int j=i+len-1;
            for(int k=i;k<=j-1;k++){
                F[i][j]=Min(F[i][j],F[i][k]+F[k+1][j]+Sum[i][j]-i+j-1);
            }
        }
    }
    Ans=F[1][T];
    printf("%d\n",Ans);
}
      
int main()
{
    freopen("prison.in","r",stdin);
    freopen("prison.out","w",stdout);
    init();
    dp();
    return 0;
}