记录编号	21377	评测结果	AAAAAAAAAA
题目名称	488.奇怪的监狱	最终得分	100
用户昵称	maxiem	是否通过	通过
代码语言	Pascal	运行时间	0.159 s
提交时间	2010-11-10 08:45:24	内存使用	3.94 MiB

program prison;
var
  data:array [1..1000] of boolean;
  f:array [0..1001,0..1001] of longint;
  tmp,j,i,p,q:integer;
procedure get(x,y:integer);
var max,tmp,i:longint;
begin
	if x<y then begin
		if x=y-1 then begin
			if data[y] or data[x] then f[x,y]:=1 else f[x,y]:=0;
		end
		else begin
	               	max:=maxlongint;
			for i:=x to y do if data[i] then begin
                               if f[x,i-1]=-1 then get(x,i-1);
                               if f[i+1,y]=-1 then get(i+1,y);
	       		       tmp:=f[x,i-1]+f[i+1,y]+y-x;
	       	               if tmp<max then max:=tmp;
                       	end;
			if max<>maxlongint then f[x,y]:=max else f[x,y]:=0;
		end;
	end;
end;
begin
	assign (input,'prison.in');
	reset (input);
	readln (p,q);
	for i:=1 to q do begin
		read (tmp);
		data[tmp]:=true;
	end;
	fillchar (f,sizeof(f),$FF);
	for i:=0 to p do for j:=i downto 0 do f[i,j]:=0;
	close (output);
	assign (output,'prison.out');
	rewrite (output);
	get(1,p);
	writeln (f[1,p]);
	close (output);
end.