记录编号	21012	评测结果	AAAAAAAAAA
题目名称	488.奇怪的监狱	最终得分	100
用户昵称	belong.zmx	是否通过	通过
代码语言	Pascal	运行时间	0.044 s
提交时间	2010-11-02 15:46:17	内存使用	0.16 MiB

program prison(input,output);
var
 n,m:longint;
 a:array[0..101]of longint;
 f:Array[0..101,0..101]of longint;
 f2:array[0..101,0..101]of boolean;
 i,j,k:longint;

function dp(l,r:longint):longint;
var
 i,j:longint;
begin
 if l>r then exit(0);
 if (f2[l,r]) then exit(f[l,r]);
 f2[l,r]:=true;
 f[l,r]:=a[r+1]-a[l-1]-2;
 j:=maxlongint;
 for i:=l to r do
  if j>dp(l,i-1)+dp(i+1,r) then
   j:=dp(l,i-1)+dp(i+1,r);
 f[l,r]:=f[l,r]+j;
 exit(f[l,r]);
end;

procedure sort(l,r:longint);
var
 i,j,mid,p:longint;
begin
 i:=l;
 j:=r;
 mid:=a[(l+r) div 2];
 repeat
  while a[i]< mid do inc(i);
  while mid< a[j] do dec(j);
  if i<=j then
  begin
   p:=a[i];
   a[i]:=a[j];
   a[j]:=p;
   inc(i);
   dec(j);
  end;
 until i >j;
 if l<j then sort(l,j);
 if i<r then sort(i,r);
end;


begin
 assign(input,'prison.in');
 reset(input);
 readln(n,m);
 for i:=1 to m do read(a[i]);
 a[0]:=0;
 a[m+1]:=n+1;
 close(input);

 sort(1,m);

 assign(output,'prison.out');
 rewrite(output);
 writeln(dp(1,m));
 close(output);
end.